Computer Science – Discrete Mathematics
Scientific paper
2008-10-10
Computer Science
Discrete Mathematics
extended abstract appeared in ISAAC 2007: Dynamic distance hereditary graphs using split decompositon. In International Sympos
Scientific paper
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give strutural and incremental characterizations, leading to optimal fully-dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on a new framework to represent the split decomposition, namely the graph-labelled trees, which also captures the modular decomposition of graphs and thereby unify these two decompositions techniques. The point of the paper is to use bijections between these graph classes and trees whose nodes are labelled by cliques and stars. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.
Gioan Emeric
Paul Christophe
No associations
LandOfFree
Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-527006