New Tools and Simpler Algorithms for Branchwidth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

New Tools and Simpler Algorithms for Branchwidth

Christophe Paul
Jan Arne Telle
  • Function : Author
  • PersonId : 889063


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.


Other [cs.OH]
Fichier principal
Vignette du fichier
D526.PDF (249.89 Ko) Télécharger le fichier

Dates and versions

lirmm-00106466 , version 1 (16-10-2006)



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



Gmail Facebook X LinkedIn More