# Dynamic Distance Hereditary Graphs Using Split Decomposition

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189506
Contributor : Christophe Paul <>
Submitted on : Wednesday, November 21, 2007 - 10:49:50 AM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM

### Identifiers

• HAL Id : lirmm-00189506, version 1

### Citation

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