Dynamic Distance Hereditary Graphs Using Split Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2007

Dynamic Distance Hereditary Graphs Using Split Decomposition

Emeric Gioan
Christophe Paul

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.
No file

Dates and versions

lirmm-00189506 , version 1 (21-11-2007)

Identifiers

  • HAL Id : lirmm-00189506 , version 1

Cite

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⟩
113 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More