Algorithmic Generation of Graphs of Branch-width ≤ k

Christophe Paul 1 Andrzej Proskurowski 2 Jan Arne Telle 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most k can be generated algorithmically as the subgraphs of k-trees. In this paper, we investigate the family of edge-maximal graphs of branchwidth k, that we call k-branches. The k-branches are, just as the k-trees, a subclass of the chordal graphs where all minimal separators have size k. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas K_{k+1} is the only subgraph-minimal k-tree, we show that for any k ≤ 7 a minimal k-branch having q maximal cliques exists for any value of q different than 3 and 5, except for k=8,q=2. We characterize subgraph-minimal k-branches for all values of k. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the k-branches.
Type de document :
Communication dans un congrès
WG'06: Graph Theoretical Concepts in Computer Science, pp.206-216, 2006, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324551
Contributeur : Christophe Paul <>
Soumis le : jeudi 25 septembre 2008 - 13:53:03
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00324551, version 1

Collections

Citation

Christophe Paul, Andrzej Proskurowski, Jan Arne Telle. Algorithmic Generation of Graphs of Branch-width ≤ k. WG'06: Graph Theoretical Concepts in Computer Science, pp.206-216, 2006, Lecture Notes in Computer Science. 〈lirmm-00324551〉

Partager

Métriques

Consultations de la notice

42