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

DOI10.1016/J.DAM.2011.05.007MaRDI QIDQ415271zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emeric Gioan, Christophe Paul

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

distance hereditary graphsfully dynamic algorithmssplit decomposition

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)

Recommendations

• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Practical and efficient split decomposition via graph-labelled trees
• A completely dynamic algorithm for split graphs
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs

Cites work

• A Combinatorial Decomposition Theory
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Recognition Algorithm for Cographs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• A note on computing set overlap classes
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• A survey of the algorithmic aspects of modular decomposition
• An O(n2) Algorithm for Undirected Split Decomposition
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
• Completely separable graphs
• Decomposition of Directed Graphs
• Decomposition of perfect graphs
• Distance labeling scheme and split decomposition
• Distance-hereditary graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Efficient graph representations
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Graph classes between parity and distance-hereditary graphs
• Graph Classes: A Survey
• Graph Drawing
• Graph minors. II. Algorithmic aspects of tree-width
• Graphs indecomposable with respect to the X-join
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• On graph powers for leaf-labeled trees
• On-line maintenance of triconnected components with SPQR-trees
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Rank-width and vertex-minors
• Reducing prime graphs and recognizing circle graphs
• Structure and linear time recognition of 3-leaf powers
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Topics in Intersection Graph Theory
• Transitiv orientierbare Graphen

Cited in

(32)

• Dynamically maintaining split graphs
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• 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
• Grammars and clique-width bounds from split decompositions
• On strict (outer-)confluent graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Modular decomposition of graphs and the distance preserving property
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Distance-hereditary comparability graphs
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Solving problems on graphs of high rank-width
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• The Structure of Level-k Phylogenetic Networks
• Practical and efficient circle graph recognition
• Practical and efficient split decomposition via graph-labelled trees
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• On strict (outer-)confluent graphs
• An exact enumeration of distance-hereditary graphs
• Split-decomposition trees with prime nodes: enumeration and random generation of cactus graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• A polynomial kernel for distance-hereditary vertex deletion
• Hypergraphs with polynomial representation: introducing \(r\)-splits
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Can you tell a tree from its branches?
• Characterization of double-arborescences and their minimum length word-representants
• Representing distance-hereditary graphs with multi-rooted trees
• Scaling limit of graph classes through split decomposition
• A note on distance-hereditary graphs whose complement is also distance-hereditary
• \(O(m\log n)\) split decomposition of strongly-connected graphs

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)