Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs
| Autor: | Emeric Gioan, Christophe Paul |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Split decomposition Distance hereditary graphs Fully dynamic algorithms Combinatorics Modular decomposition Indifference graph Pathwidth 010201 computation theory & mathematics Chordal graph Permutation graph Discrete Mathematics and Combinatorics Cograph Maximal independent set Split graph 0101 mathematics Algorithm Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics. 160(6):708-733 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2011.05.007 |
| Popis: | 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 structural and incremental characterizations, leading to optimal fully dynamic 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 (and also the modular decomposition). 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect