Skip to Main content Skip to Navigation
Conference papers

New Tools and Simpler Algorithms for Branchwidth

Christophe Paul 1 Jan Arne Telle
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We provide new tools, such as k-troikas and good subtree-representations, that allow us to give fast and simple algorithms computing branchwidth. We show that a graph G has branchwidth at most k if and only if it is a subgraph of a chordal graph in which every maximal clique has a k-troika respecting its minimal separators. Moreover, if G itself is chordal with clique tree T then such a chordal supergraph exists having clique tree a minor of T. We use these tools to give a straightforward O(m + n + q 2 ) algorithm computing branchwidth for an interval graph on m edges, n vertices and q maximal cliques. We also prove a conjecture of F. Mazoit [13] by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106466
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, October 16, 2006 - 8:29:28 AM
Last modification on : Saturday, September 21, 2019 - 6:37:11 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 7:42:27 PM

File

Identifiers

Collections

Citation

Christophe Paul, Jan Arne Telle. New Tools and Simpler Algorithms for Branchwidth. ESA: European Symposium on Algorithms, Oct 2005, Palma de Mallorca, Spain. pp.379-390, ⟨10.1007/11561071_35⟩. ⟨lirmm-00106466⟩

Share

Metrics

Record views

168

Files downloads

116