Computing the branchwidth of interval graphs
From MaRDI portal
Publication:1764810
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
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