Practical and efficient split decomposition via graph-labelled trees
From MaRDI portal
Publication:472485
DOI10.1007/s00453-013-9752-9zbMath1303.05191arXiv1104.3283OpenAlexW1861909104MaRDI QIDQ472485
Emeric Gioan, Christophe Paul, Marc Tedder, Derek Gordon 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
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Solving Problems on Graphs of High Rank-Width ⋮ Grammars and clique-width bounds from split decompositions ⋮ Circle graph isomorphism in almost linear time ⋮ Solving problems on graphs of high rank-width ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Practical and efficient circle graph recognition ⋮ On complexities of minus domination ⋮ Diamond-free circle graphs are Helly circle ⋮ Splitting cubic circle graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- A survey of the algorithmic aspects of modular decomposition
- Practical and efficient circle graph recognition
- The strong perfect graph theorem
- Completely separable graphs
- Reducing prime graphs and recognizing circle graphs
- On the extension of bipartite to parity graphs
- Graph classes between parity and distance-hereditary graphs
- Circle graph obstructions
- LexBFS-orderings and powers of chordal graphs
- Logical description of context-free graph languages
- Efficient graph representations
- Distance labeling scheme and split decomposition
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Algorithmic graph theory and perfect graphs
- Handle-rewriting hypergraph grammars
- Recognizing Berge graphs
- Rank-width and vertex-minors
- Linear Time Split Decomposition Revisited
- A Combinatorial Decomposition Theory
- Decomposition of Directed Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithmic Aspects of Vertex Elimination on Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Recognition of Circle Graphs
- An O(n2) Algorithm for Undirected Split Decomposition
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Recognizing circle graphs in polynomial time
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Transitiv orientierbare Graphen
- Graph-Theoretic Concepts in Computer Science
- Graph Drawing
This page was built for publication: Practical and efficient split decomposition via graph-labelled trees
