# 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.
Type de document :
Communication dans un congrès
ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.41-51, 2007, Lecture Notes in Computer Science

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189506
Contributeur : Christophe Paul <>
Soumis le : mercredi 21 novembre 2007 - 10:49:50
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

### Identifiants

• 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, 2007, Lecture Notes in Computer Science. 〈lirmm-00189506〉

### Métriques

Consultations de la notice