Computing the branchwidth of interval graphs

DOI10.1016/j.dam.2004.01.015zbMath1084.05068MaRDI QIDQ1764810

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

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.015

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Branchwidth of chordal graphs, Computing branchwidth via efficient triangulations and blocks, Mixed search number and linear-width of interval and split graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Graph minors. X: Obstructions to tree-decomposition
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Upper bounds on the size of obstructions and intertwines
• Call routing and the ratcatcher
• Treewidth. Computations and approximations
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Complexity of Finding Embeddings in a k-Tree
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Graphs with Branchwidth at Most Three
• Constructive linear time algorithms for branchwidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth