Dynamic Distance Hereditary Graphs Using Split Decomposition

Emeric Gioan 1 Christophe Paul 2, 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.
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
Liste complète des métadonnées

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

Collections

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〉

Partager

Métriques

Consultations de la notice

139