New Tools and Results for Branchwidth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2005

New Tools and Results for Branchwidth

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

Abstract

We provide new tools for the study of branchwidth of graphs, such as $k$-troikas and good subtree-representations, that allow us to give several new results. 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 \cite{Maz04a} by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees. Finally, we propose a characterization of $k$-branches, namely those graphs of branchwidth $k$ having a maximal set of edges.

Keywords

Domains

Other [cs.OH]
No file

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00106678 , version 1

Cite

Christophe Paul, Jan Arne Telle. New Tools and Results for Branchwidth. 05017, 2005, pp.14. ⟨lirmm-00106678⟩
45 View
0 Download

Share

More