An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs

DOI10.1007/978-3-540-70918-3_30MaRDI QIDQ3590946zbMATH OpenOpenAlexFDO

Authors Marc Tedder, Derek G. Corneil

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

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

zbMATH Keywords

distance-hereditarycographdynamic algorithmgraph recognition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Recommendations

• scientific article; zbMATH DE number 2089962
• scientific article; zbMATH DE number 815104
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• scientific article; zbMATH DE number 1303031
• Linear-time algorithm for paired-domination on distance-hereditary graphs
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• On an extension of distance-hereditary graphs

Cited in

(9)

• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• 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
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Fully dynamic recognition of proper circular-arc graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Fully dynamic representations of interval graphs

This page was built for publication: An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs

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