Practical and efficient split decomposition via graph-labelled trees

DOI10.1007/S00453-013-9752-9MaRDI QIDQ472485zbMATH OpenOpenAlexFDO

Authors Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil

Publication date 19 November 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.3283

zbMATH Keywords

decomposition theorysplit decomposition

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time $O(n+m)alpha(n+m)$, where $alpha$ is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear-time split decomposition algorithm [Dahlhaus'00], which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper [Gioan et al.] uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm.

Recommendations

• Practical and efficient circle graph recognition
• An O(n2) Algorithm for Undirected Split Decomposition
• \(O(m \log n)\) split decomposition of strongly connected graphs
• Recognition of Circle Graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs

Cites work

• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A Combinatorial Decomposition Theory
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• A survey of the algorithmic aspects of modular decomposition
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Circle graph obstructions
• Completely separable graphs
• Decomposition of Directed Graphs
• Distance labeling scheme and split decomposition
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient graph representations
• Graph Drawing
• Graph classes between parity and distance-hereditary graphs
• Graph-Theoretic Concepts in Computer Science
• Handle-rewriting hypergraph grammars
• Introduction to algorithms
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• LexBFS-orderings and powers of chordal graphs
• Linear time split decomposition revisited
• Logical description of context-free graph languages
• On the extension of bipartite to parity graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Polynomial-time recognition of clique-width 3 graphs
• Practical and efficient circle graph recognition
• Rank-width and vertex-minors
• Recognition of Circle Graphs
• Recognizing Berge graphs
• Recognizing circle graphs in polynomial time
• Reducing prime graphs and recognizing circle graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• The strong perfect graph theorem
• Transitiv orientierbare Graphen

Cited in

(14)

• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Extending partial representations of circle graphs in near-linear time
• On complexities of minus domination
• Splitting cubic circle graphs
• A survey of the algorithmic aspects of modular decomposition
• Practical and efficient circle graph recognition
• Solving problems on graphs of high rank-width
• Diamond-free circle graphs are Helly circle
• Grammars and clique-width bounds from split decompositions
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• Prime Testing for the Split Decomposition of a Graph
• Circle graph isomorphism in almost linear time
• Linear time split decomposition revisited
• Solving problems on graphs of high rank-width

This page was built for publication: Practical and efficient split decomposition via graph-labelled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472485)