A partial k-arboretum of graphs with bounded treewidth

DOI10.1016/S0304-3975(97)00228-4zbMath0912.68148WikidataQ29542840 ScholiaQ29542840MaRDI QIDQ1274912

Hans L. Bodlaender

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

treewidth; partial \(k\)-tree; graph classes

Mathematics Subject Classification ID

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

Related Items

Monadic second-order definable text languages, Helicopter search problems, bandwidth and pathwidth

Cites Work

• Graph minors. XXII. Irrelevant vertices in linkage problems
• On the complexity of embedding planar graphs to minimize certain distance measures
• A simple linear-time algorithm for finding path-decompositions of small width
• Mixed searching and proper-path-width
• Hyperedge replacement: grammars and languages
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Forbidden minors characterization of partial 3-trees
• A lower bound on the area of permutation layouts
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. V. Excluding a planar graph
• Nonconstructive advances in polynomial-time complexity
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The vertex separation number of a graph equals its path-width
• Complexity of path-forming games
• Characterizations of outerplanar graphs
• On hyperedge replacement and BNLC graph grammars
• Graph minors. XI: Circuits on a surface
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• The vertex separation and search number of a graph
• Obstruction set isolation for the gate matrix layout problem
• The nonexistence of reduction rules giving an embedding into a \(k\)-tree
• Quickly excluding a planar graph
• Treewidth. Computations and approximations
• Fugitive-search games on graphs and related parameters
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XVII: Taming a vortex
• Graph minors. IX: Disjoint crossed paths
• Searching and pebbling
• On simple characterizations of k-trees
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XII: Distance on a surface
• Triangulating graphs without asteroidal triples
• Graph minors. XV: Giant steps
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Chordal Graphs
• The Role of Elimination Trees in Sparse Factorization
• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Graph expressions and graph rewritings
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• A Separator Theorem for Planar Graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On Linear Time Minor Tests with Depth-First Search
• On Time Versus Space
• An algebraic theory of graph reduction
• Approximation algorithms for NP-complete problems on planar graphs
• ON DISJOINT CYCLES
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Domino Treewidth
• The Pathwidth and Treewidth of Cographs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Recontamination does not help to search a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item