Dynamic Distance Hereditary Graphs Using Split Decomposition
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 distan
- PDF / 447,421 Bytes
- 11 Pages / 430 x 660 pts Page_size
- 100 Downloads / 222 Views
Introduction
Motivated by their practical applications as well as by their related theoretical challenges, dynamic graph algorithms have received particular attention over the last few years [12]. Solving a problem on a dynamic graph consists of an algorithm that, under a series of graph modifications (vertex or edge modification), updates a data structure supporting elementary queries (e.g. adjacency). Let us note that the series of modifications to which the graph is submitted is not known in advance. To be of interest, such an algorithm should not recompute a solution from scratch. In order to ensure locality of the computation, most of the known dynamic graph algorithms are based on decomposition techniques. For example, the SPQR-tree data structure has been introduced in order to dynamically maintain the 3-connected components of a graph which allows on-line planarity testing [2]. This paper considers the dynamic representation problem which asks for the maintenance of a representation of a dynamic graph as long as a certain property Π is satisfied. Existing literature on this problem includes representation of chordal graphs [18], proper interval graphs [16], cographs [21], directed cographs [7], permutation graphs [8]. The data structures used for the last four results are strongly related to the modular decomposition tree [14]. The split decomposition (also called 1-join decomposition), introduced by Cunningham [9],
Research supported by the French ANR project “Graph Decompositions and Algorithms (GRAAL)”. Research conducted while C. Paul was on Sabbatical at School of Computer Science, McGill University, Montr´eal, Canada.
T. Tokuyama (Ed.): ISAAC 2007, LNCS 4835, pp. 41–51, 2007. c Springer-Verlag Berlin Heidelberg 2007
42
E. Gioan and C. Paul
is a generalization of the modular decomposition. A natural question is to ask whether the split decomposition can be used to dynamically represent wider graph families? We answer positively to this question. The algorithmic aspects of the split decomposition, unlike the modular decomposition, are not well understood. For instance, totally decomposable graphs are known to be the distance hereditary graphs [1,15], which form an interesting family of graphs for several reasons: they generalize the well-known cographs [5], which are totally decomposable by the modular decomposition; they are the graphs of rankwidth 1 [20] and are among the elementary graphs of cliquewidth 3 [4]; they also have various theoretical characterizations... Computing the split decomposition in linear time [10] is very complicated. It follows that most of the known algorithms (even recent ones) operating on distance hereditary graphs do not rely on the split decomposition but rather on a heavy breadthfirst search layering characterization [1], or on some ad-hoc (rooted) tree decompositions [3,17,23]. Similarly the recent O(1) edge-only dynamic recognition algorithm [6] is based on the BFS layering characterization. In this paper, we revisit the split decomposition theory [9] under the
Data Loading...
