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

New Tools and Results for Branchwidth

Christophe Paul
Jan Arne Telle
  • Fonction : Auteur
  • PersonId : 889063

Résumé

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.

Mots clés

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00106678 , version 1

Citer

Christophe Paul, Jan Arne Telle. New Tools and Results for Branchwidth. 05017, 2005, pp.14. ⟨lirmm-00106678⟩
52 Consultations
0 Téléchargements

Partager

More