A partial k-arboretum of graphs with bounded treewidth

DOI10.1016/S0304-3975(97)00228-4zbMATH Open0912.68148OpenAlexW2087083200WikidataQ29542840 ScholiaQ29542840MaRDI QIDQ1274912FDOQ1274912

Authors: 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

Recommendations

• Publication:4734761
• scientific article; zbMATH DE number 4215390
• A lower bound for the vertex boundary-width of complete \(k\)-ary trees
• Partitioning graphs of bounded tree-width
• scientific article; zbMATH DE number 932194
• Bounds on the arboricities of connected graphs
• scientific article; zbMATH DE number 7731184
• A managed Bayesian risk approach for decision making alternatives
• Treewidth of the generalized Kneser graphs
• A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths

zbMATH Keywords

treewidthgraph classespartial \(k\)-tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (only showing first 100 items - show all)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Spanning tree congestion of \(k\)-outerplanar graphs
• Sparse graphs of high gonality
• Maximum induced forests in graphs of bounded treewidth
• Computing optimal Steiner trees in polynomial space
• Random graphs containing few disjoint excluded minors
• On computing the Hamiltonian index of graphs
• On the separation profile of infinite graphs
• Genus distributions for iterated claws
• Grid minors in damaged grids
• Nordhaus-Gaddum for treewidth
• Genus distribution of \(P_3 \mathop\square P_n\)
• Graph decompositions for cartesian products
• Graphs without large apples and the maximum weight independent set problem
• On the complexity of some subgraph problems
• Treewidth computations. II. Lower bounds
• On proper labellings of graphs with minimum label sum
• On switching classes, NLC-width, cliquewidth and treewidth
• A 3-approximation for the pathwidth of Halin graphs
• A local search algorithm for branchwidth
• Safe separators for treewidth
• The treewidth and pathwidth of hypercubes
• Monadic second-order model-checking on decomposable matroids
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• A note on planar graphs with large width parameters and small grid-minors
• The inverse inertia problem for the complements of partial \(k\)-trees
• Algorithms for finding distance-edge-colorings of graphs
• A \(c^k n\) 5-approximation algorithm for treewidth
• On minimum average stretch spanning trees in polygonal 2-trees
• A faster polynomial-space algorithm for Max 2-CSP
• Treewidth lower bounds with brambles
• On tree-partition-width
• Complexity results for the spanning tree congestion problem
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Call control with \(k\) rejections
• Computing branchwidth via efficient triangulations and blocks
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Clique-width of countable graphs: A compactness property.
• On Computing the Hamiltonian Index of Graphs
• Characterizing graphs of small carving-width
• Tree decompositions of graphs: saving memory in dynamic programming
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• On the minimum corridor connection problem and other generalized geometric problems
• From tree-decompositions to clique-width terms
• Lower bounds on the pathwidth of some grid-like graphs
• Completely independent spanning trees in (partial) \(k\)-trees
• Approximation algorithms for digraph width parameters
• On triangulating \(k\)-outerplanar graphs
• Derivation of algorithms for cutwidth and related graph layout parameters
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Faster Steiner Tree Computation in Polynomial-Space
• How to Cut a Graph into Many Pieces
• How to compute digraph width measures on directed co-graphs
• Matrix norms and rapid mixing for spin systems
• The complexity of minimum-length path decompositions
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• On the parameterized complexity of non-monotonic logics
• Linear-time algorithm for sliding tokens on trees
• Computing bond orders in molecule graphs
• Fractals for kernelization lower bounds
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• The height of random k‐trees and related branching processes
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• The behavior of clique-width under graph operations and graph transformations
• Obstructions for linear rank-width at most 1
• Helicopter search problems, bandwidth and pathwidth
• An efficient tree decomposition method for permanents and mixed discriminants
• The pagenumber of \(k\)-trees is \(O(k)\)
• Tree-decompositions with bags of small diameter
• Pebbling in semi-2-trees
• On making a distinguished vertex of minimum degree by vertex deletion
• Planar 3-SAT with a clause/variable cycle
• Tree-width dichotomy
• Fast Robber in Planar Graphs
• Critical elements in combinatorially closed families of graph classes
• A generic convolution algorithm for join operations on tree decompositions
• Clustered 3-colouring graphs of bounded degree
• On some tractable and hard instances for partial incentives and target set selection
• Weighted total acquisition
• A note on integral generalized flows in directed partial 2-trees
• Local WL invariance and hidden shades of regularity
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Graph product structure for non-minor-closed classes
• A new approach on locally checkable problems
• Edge clique partition in \((k,\ell)\)-graphs
• FPT algorithms to enumerate and count acyclic and totally cyclic orientations
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Gallai's conjecture for graphs with treewidth 3
• On minimizing the maximum color for the 1-2-3 conjecture
• Transversals of longest cycles in partial k‐trees and chordal graphs
• Improved bounds for track numbers of planar graphs
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• An improved planar graph product structure theorem
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• Beating treewidth for average-case subgraph isomorphism
• Finding and counting permutations via CSPs
• On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
• Title not available (Why is that?)

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

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