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

DOI10.1007/978-3-540-70918-3_30zbMath1186.68341OpenAlexW1738403920MaRDI QIDQ3590946

Marc Tedder, Derek Gordon 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

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

Related Items (6)

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ 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 ⋮ Fully dynamic representations of interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Fully dynamic recognition of proper circular-arc graphs

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