Dynamic Distance Hereditary Graphs Using Split Decomposition

DOI10.1007/978-3-540-77120-3_6MaRDI QIDQ5387744zbMATH OpenOpenAlexFDO

Authors Emeric Gioan, Christophe Paul

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Recommendations

• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• A completely dynamic algorithm for split graphs
• Distance-hereditary comparability graphs

Cites work

• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 2089962 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Recognition Algorithm for Cographs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Completely separable graphs
• Decomposition of Directed Graphs
• Distance-hereditary graphs
• Graph Drawing
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• On-Line Planarity Testing
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Rank-width and vertex-minors
• Recognition of Circle Graphs
• Separator based sparsification for dynamic planar graph algorithms
• Topics in Intersection Graph Theory
• Transitiv orientierbare Graphen

Cited in

(17)

• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Practical and efficient split decomposition via graph-labelled trees
• Word-representability of graphs with respect to split recomposition
• A completely dynamic algorithm for split graphs
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
• Dynamically maintaining split graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Distance-hereditary comparability graphs
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Solving problems on graphs of high rank-width
• Hypergraphs with polynomial representation: introducing \(r\)-splits
• A survey of the algorithmic aspects of modular decomposition
• The axiomatic characterization of the interval function of distance hereditary graphs
• Practical and efficient circle graph recognition
• Solving problems on graphs of high rank-width

This page was built for publication: Dynamic Distance Hereditary Graphs Using Split Decomposition

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