A partial k-arboretum of graphs with bounded treewidth

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

Hans L. Bodlaender

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00228-4

zbMATH Keywords

treewidthpartial \(k\)-treegraph classes

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ Clustered 3-colouring graphs of bounded degree ⋮ On the Complexity of Finding a Potential Community ⋮ Bounding the search number of graph products ⋮ Fast Robber in Planar Graphs ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ On spectra of sentences of monadic second order logic with counting ⋮ On the pathwidth of hyperbolic 3-manifolds ⋮ Computing Bond Types in Molecule Graphs ⋮ Simultaneously dominating all spanning trees of a graph ⋮ Treewidth of Cartesian Products of Highly Connected Graphs ⋮ Enumerating graph embeddings and partial-duals by genus and Euler genus ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Characterizations and directed path-width of sequence digraphs ⋮ Separating layered treewidth and row treewidth ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Transversals of longest cycles in partial k‐trees and chordal graphs ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ PTAS for Sparse General-valued CSPs ⋮ Connected search for a lazy robber ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Splitting plane graphs to outerplanarity ⋮ Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width ⋮ On the transversal number of rank \(k\) hypergraphs ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Graphs of linear growth have bounded treewidth ⋮ Edge deletion to tree-like graph classes ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ On Ramsey Size-Linear Graphs and Related Questions ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Induced subgraphs and path decompositions ⋮ Graph product structure for non-minor-closed classes ⋮ On the linear arboricity of graphs with treewidth at most four ⋮ Embedding and the rotational dimension of a graph containing a clique ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ Extended MSO model checking via small vertex integrity ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Extended double covers and homomorphism bounds of signed graphs ⋮ Improved Bounds for Track Numbers of Planar Graphs ⋮ Unnamed Item ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Chromatic index, treewidth and maximum degree ⋮ Compact and localized distributed data structures ⋮ Weighted Treewidth Algorithmic Techniques and Results ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Unnamed Item ⋮ Chromatic index, treewidth and maximum degree ⋮ Random graphs containing few disjoint excluded minors ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ The pagenumber of \(k\)-trees is \(O(k)\) ⋮ To Approximate Treewidth, Use Treelength! ⋮ Unnamed Item ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ A meta-theorem for distributed certification ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ The problem of path decomposition for graphs with treewidth at most 4 ⋮ Unnamed Item ⋮ Finding cut-vertices in the square roots of a graph ⋮ On the design of efficient ATM routing schemes ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Unnamed Item ⋮ On Tuza's conjecture for triangulations and graphs with small treewidth ⋮ Maximum cuts in edge-colored graphs ⋮ Unnamed Item ⋮ Non-preemptive tree packing ⋮ On Tuza's conjecture for triangulations and graphs with small treewidth ⋮ Better bounds for poset dimension and boxicity ⋮ 2-colored point-set embeddings of partial 2-trees ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ The Valve Location Problem in Simple Network Topologies ⋮ Unnamed Item ⋮ Planar 3-SAT with a clause/variable cycle ⋮ AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH ⋮ Treewidth of the Line Graph of a Complete Graph ⋮ The Size Ramsey Number of Graphs with Bounded Treewidth ⋮ Tractable minor-free generalization of planar zero-field Ising models ⋮ The height of random k‐trees and related branching processes ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ Critical elements in combinatorially closed families of graph classes ⋮ A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ A Survey on Spanning Tree Congestion

Cites Work

• 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
• 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

This page was built for publication: A partial k-arboretum of graphs with bounded treewidth