Skip to Main content Skip to Navigation
Conference papers

Dynamic Distance Hereditary Graphs Using Split Decomposition

Emeric Gioan 1 Christophe Paul 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity $O(d)$, where $d$ is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.
Document type :
Conference papers
Complete list of metadata
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Wednesday, November 21, 2007 - 10:49:50 AM
Last modification on : Friday, October 22, 2021 - 3:07:29 PM


  • HAL Id : lirmm-00189506, version 1



Emeric Gioan, Christophe Paul. Dynamic Distance Hereditary Graphs Using Split Decomposition. ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.41-51. ⟨lirmm-00189506⟩



Record views