Back to Search
Start Over
New Tools and Simpler Algorithms for Branchwidth.
- Source :
- Algorithms - ESA 2005; 2005, p379-390, 12p
- Publication Year :
- 2005
-
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+q2) 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540291183
- Database :
- Supplemental Index
- Journal :
- Algorithms - ESA 2005
- Publication Type :
- Book
- Accession number :
- 32864794
- Full Text :
- https://doi.org/10.1007/11561071_35