Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
From MaRDI portal
Publication:415271
DOI10.1016/j.dam.2011.05.007zbMath1236.05162OpenAlexW2105085476WikidataQ56475002 ScholiaQ56475002MaRDI QIDQ415271
Publication date: 11 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.05.007
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items
Solving Problems on Graphs of High Rank-Width ⋮ Topology and counting of real algebraic curves ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On Strict (Outer-)Confluent Graphs ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Grammars and clique-width bounds from split decompositions ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ On strict (outer-)confluent graphs ⋮ Solving problems on graphs of high rank-width ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Enumerations, forbidden subgraph characterizations, and the split-decomposition ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ The Structure of Level-k Phylogenetic Networks ⋮ Modular decomposition of graphs and the distance preserving property
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- Structure and linear time recognition of 3-leaf powers
- Completely separable graphs
- A note on computing set overlap classes
- Decomposition of perfect graphs
- Distance-hereditary graphs
- Reducing prime graphs and recognizing circle graphs
- Graph classes between parity and distance-hereditary graphs
- Graphs indecomposable with respect to the X-join
- Efficient graph representations
- Distance labeling scheme and split decomposition
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- On-line maintenance of triconnected components with SPQR-trees
- Fully dynamic recognition algorithm and certificate for directed cographs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Rank-width and vertex-minors
- On Graph Powers for Leaf-Labeled Trees
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
- A Linear Recognition Algorithm for Cographs
- Graph minors. II. Algorithmic aspects of tree-width
- A Combinatorial Decomposition Theory
- Decomposition of Directed Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- An O(n2) Algorithm for Undirected Split Decomposition
- 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
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Transitiv orientierbare Graphen
- Graph Drawing
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
