New branchwidth territories

DOI10.1007/3-540-49116-3_16MaRDI QIDQ4251049zbMATH OpenFDO

Authors Ton Kloks, Jan Kratochvíl, Haiko Müller

Publication date 2 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49116-3_16

zbMATH Keywords

algorithmbipartite graphsbranchwidthNP-completepermutation graphssplit graphstreewidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Review text

The notion of branchwidth recently received more and more interest, also because of its connections to the notion of treewidth. In this paper, a number of results on the complexity of determining the branchwidth for special classes of graphs are obtained. It is shown that the branchwidth is NP-complete for split graphs, and for bipartite graphs. An algorithm that uses \(O(n^3\log n)\) time for computing the branchwidth of an interval is given. The method generalizes to permutation graphs, and, more generally, to \(d\)-trapezoid graphs. For the entire collection see [Zbl 0909.00052].

Recommendations

• Branching out
• Bounding branch-width
• Branch groups
• Branching in the landscape of possibilities
• Local branching
• Editorial: new branches, old roots
• Testing branch-width
• New branching rules induced by plethysm
• Algorithms – ESA 2005

Cited in

(8)

• Edge-maximal graphs of branchwidth k: The k-branches
• NP-hard and linear variants of hypergraph partitioning
• Computing the branchwidth of interval graphs
• Graphs with Branchwidth at Most Three
• Algorithms – ESA 2005
• Testing branch-width
• Branchwidth of chordal graphs
• Computing branchwidth via efficient triangulations and blocks

This page was built for publication: New branchwidth territories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4251049)