Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs

DOI10.1016/J.DAM.2011.05.007zbMATH Open1236.05162DBLPjournals/dam/GioanP12OpenAlexW2105085476WikidataQ56475002 ScholiaQ56475002MaRDI QIDQ415271FDOQ415271

Christophe Paul, Emeric Gioan

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

zbMATH Keywords

split decompositiondistance hereditary graphsfully dynamic algorithms

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Graphs indecomposable with respect to the X-join
• Graph Classes: A Survey
• Efficient graph representations
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Transitiv orientierbare Graphen
• Distance-hereditary graphs
• Rank-width and vertex-minors
• A Combinatorial Decomposition Theory
• A Linear Recognition Algorithm for Cographs
• Decomposition of Directed Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Reducing prime graphs and recognizing circle graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• A survey of the algorithmic aspects of modular decomposition
• On graph powers for leaf-labeled trees
• Structure and linear time recognition of 3-leaf powers
• Decomposition of perfect graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Graph classes between parity and distance-hereditary graphs
• 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
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary 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
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Graph Drawing
• Completely separable graphs
• A note on computing set overlap classes

Cited In (21)

• The Structure of Level-k Phylogenetic Networks
• \(O(m\log n)\) split decomposition of strongly-connected graphs
• On strict (outer-)confluent graphs
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Hypergraphs with polynomial representation: introducing \(r\)-splits
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Practical and efficient split decomposition via graph-labelled trees
• Practical and efficient circle graph recognition
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Grammars and clique-width bounds from split decompositions
• A polynomial kernel for distance-hereditary vertex deletion
• On Strict (Outer-)Confluent Graphs
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Solving problems on graphs of high rank-width
• Topology and counting of real algebraic curves
• Modular decomposition of graphs and the distance preserving property
• Solving Problems on Graphs of High Rank-Width

This page was built for publication: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs

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