Computing the branchwidth of interval graphs

DOI10.1016/J.DAM.2004.01.015MaRDI QIDQ1764810zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Jan Kratochvíl, 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

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

Recommendations

• scientific article; zbMATH DE number 1304318
• Branchwidth of chordal graphs
• Algorithms – ESA 2005
• Practical algorithms for branch-decompositions of planar graphs
• Computing branchwidth via efficient triangulations and blocks

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4008410 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1304318 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Call routing and the ratcatcher
• Complexity of Finding Embeddings in a k-Tree
• Constructive linear time algorithms for branchwidth
• Graph minors. I. Excluding a forest
• Graph minors. X: Obstructions to tree-decomposition
• Graphs with Branchwidth at Most Three
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth. Computations and approximations
• Upper bounds on the size of obstructions and intertwines

Cited in

(10)

• Algorithms – ESA 2005
• 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
• Tangle bases: Revisited
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Graph-Theoretic Concepts in Computer Science
• Mixed search number and linear-width of interval and split graphs
• scientific article; zbMATH DE number 3861209 (Why is no real title available?)
• Mixed Search Number and Linear-Width of Interval and Split Graphs

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

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