Split Decomposition and Graph-Labelled Trees: Characterizations and Fully-Dynamic Algorithms for Totally Decomposable Graphs

Emeric Gioan 1 Christophe Paul 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 fullydynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs. The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, 160 (6), pp.708-733
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00783420
Contributeur : Emeric Gioan <>
Soumis le : vendredi 1 février 2013 - 09:45:22
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00783420, version 1

Collections

Citation

Emeric Gioan, Christophe Paul. Split Decomposition and Graph-Labelled Trees: Characterizations and Fully-Dynamic Algorithms for Totally Decomposable Graphs. Discrete Applied Mathematics, Elsevier, 2012, 160 (6), pp.708-733. 〈lirmm-00783420〉

Partager

Métriques

Consultations de la notice

131