Branchwidth of Chordal Graphs

Christophe Paul 1 Jan Arne Telle 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper revisits the ‘branchwidth territories' of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called k-troikas: three sets of size at most k each are a k-troika of set S, if any two have union S. We give a straightforward O(m+n+q2) algorithm, computing branchwidth for an interval graph on m edges, n vertices and q maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2009, 157 (12), pp.2718-2725
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394553
Contributeur : Christophe Paul <>
Soumis le : vendredi 12 juin 2009 - 08:31:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00394553, version 1

Collections

Citation

Christophe Paul, Jan Arne Telle. Branchwidth of Chordal Graphs. Discrete Applied Mathematics, Elsevier, 2009, 157 (12), pp.2718-2725. 〈lirmm-00394553〉

Partager

Métriques

Consultations de la notice

83