Computing the branchwidth of interval graphs

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

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

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

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Tangle bases: Revisited ⋮ Mixed Search Number and Linear-Width of Interval and Split Graphs ⋮ Branchwidth of chordal graphs ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ 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

This page was built for publication: Computing the branchwidth of interval graphs