Practical and efficient split decomposition via graph-labelled trees

DOI10.1007/S00453-013-9752-9zbMATH Open1303.05191arXiv1104.3283OpenAlexW1861909104MaRDI QIDQ472485FDOQ472485

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

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• Grammars and clique-width bounds from split decompositions
• 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)