A partial k-arboretum of graphs with bounded treewidth

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

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

treewidth partial $k$-tree graph classes

Mathematics Subject Classification ID

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

Related Items

Perfect edge domination and efficient edge domination in graphs, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Bounded clique cover of some sparse graphs, Call control with $k$ rejections, Graph separators: A parameterized view, A new approach on locally checkable problems, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, FPT algorithms to enumerate and count acyclic and totally cyclic orientations, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Tree-width dichotomy, Constant factor approximation for the weighted partial degree bounded edge packing problem, An improved planar graph product structure theorem, Monadic second-order definable text languages, A general framework for path convexities, Probabilistic reasoning with graphical security models, On quasi-planar graphs: clique-width and logical description, 1-page and 2-page drawings with bounded number of crossings per edge, Treewidth and gonality of glued grid graphs, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, A width parameter useful for chordal and co-comparability graphs, Postman problems on series-parallel mixed graphs, Entanglement and the complexity of directed graphs, Approximate search strategies for weighted trees, On the separation profile of infinite graphs, Helicopter search problems, bandwidth and pathwidth, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Interval degree and bandwidth of a graph, The multi-stripe travelling salesman problem, Structure and enumeration of $K_4$-minor-free links and link-diagrams, Query efficient implementation of graphs of bounded clique-width, Size-treewidth tradeoffs for circuits computing the element distinctness function, The many facets of upper domination, Structural parameters for scheduling with assignment restrictions, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Trimming of graphs, with application to point labeling, Recognition of directed acyclic graphs by spanning tree automata, Clique-width of countable graphs: A compactness property., On minimizing the maximum color for the 1-2-3 conjecture, How to compute digraph width measures on directed co-graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Weighted total acquisition, Finding a potential community in networks, 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, Coloring invariants of knots and links are often intractable, Computational complexity of the vertex cover problem in the class of planar triangulations, Edge clique partition in $(k,\ell)$-graphs, Inclusion/exclusion meets measure and conquer, $2K_2$-partition of some classes of graphs, Tree decompositions with small cost, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, On some tractable and hard instances for partial incentives and target set selection, Counting models for 2SAT and 3SAT formulae, The treewidth of proofs, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Pursuing a fast robber on a graph, Optimization for first order Delaunay triangulations, Representing graphs as the intersection of cographs and threshold graphs, Tree-coloring problems of bounded treewidth graphs, Beating treewidth for average-case subgraph isomorphism, Finding and counting permutations via CSPs, Independent-set reconfiguration thresholds of hereditary graph classes, On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines, On exteriority notions in book embeddings and treewidth, Derivation of algorithms for cutwidth and related graph layout parameters, Universal augmentation schemes for network navigability, Notes on graph product structure theory, On two techniques of combining branching and treewidth, Approximating the maximum clique minor and some subgraph homeomorphism problems, Horton-Strahler number, rooted pathwidth and upward drawings of trees, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, On tree-partition-width, Nondeterministic graph searching: from pathwidth to treewidth, Treewidth of graphs with balanced separations, Complexity results for minimum sum edge coloring, Computing the number of $k$-component spanning forests of a graph with bounded treewidth, Computational properties of argument systems satisfying graph-theoretic constraints, On problems without polynomial kernels, Comparing linear width parameters for directed graphs, Pathwidth of cubic graphs and exact algorithms, Computing the chromatic number using graph decompositions via matrix rank, On the complexity of singly connected vertex deletion, Revising Johnson's table for the 21st century, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, On minimum average stretch spanning trees in polygonal 2-trees, The complexity of finding harmless individuals in social networks, Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph, A meta-theorem for distributed certification, The complexity of the $K_{n,n}$-problem for node replacement graph languages, On sparsification for computing treewidth, Capacitated domination: problem complexity and approximation algorithms, Synthesizing structured reactive programs via deterministic tree automata, On maximum independent set of categorical product and ultimate categorical ratios of graphs, A generic convolution algorithm for join operations on tree decompositions, Parameterized complexity of $(A,\ell)$-path packing, On proper labellings of graphs with minimum label sum, 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, 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, Complexity and monotonicity results for domination games, Safe separators for treewidth, The treewidth and pathwidth of hypercubes, On finding short resolution refutations and small unsatisfiable subsets, Structural tractability of counting of solutions to conjunctive queries, On computational complexity of graph inference from counting, Computing the zig-zag number of directed graphs, Algorithms for graphs of bounded treewidth via orthogonal range searching, On the minimum corridor connection problem and other generalized geometric problems, A note on total and list edge-colouring of graphs of tree-width 3, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Approximate tree decompositions of planar graphs in linear time, Computational social choice for coordination in agent networks, Constraint satisfaction with bounded treewidth revisited, Dense trees: a new look at degenerate graphs, Roman domination in subgraphs of grids, Online promise problems with online width metrics, Jumping robbers in digraphs, Characterizing width two for variants of treewidth, Exact algorithms and applications for tree-like Weighted Set Cover, Conjunctive query evaluation by search-tree revisited, Matching interdiction, The parameterized complexity of local search for TSP, more refined, Achievable sets, brambles, and sparse treewidth obstructions, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Satisfiability of acyclic and almost acyclic CNF formulas, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Maximum induced forests in graphs of bounded treewidth, Splitting trees at vertices, Genus distributions for iterated claws, Grid minors in damaged grids, On graph thickness, geometric thickness, and separator theorems, Courcelle's theorem -- a game-theoretic approach, Graph classes with and without powers of bounded clique-width, Nordhaus-Gaddum for treewidth, Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs, On the treewidth of toroidal grids, The complexity of minimum convex coloring, Scale free properties of random $k$-trees, A faster polynomial-space algorithm for Max 2-CSP, Approximation of minimum weight spanners for sparse graphs, On switching classes, NLC-width, cliquewidth and treewidth, Segment representation of a subclass of co-planar graphs, The minimum semidefinite rank of the complement of partial $k$-trees, A note on planar graphs with large width parameters and small grid-minors, Computing bond orders in molecule graphs, An efficient tree decomposition method for permanents and mixed discriminants, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph, Digraph decompositions and monotonicity in digraph searching, Local search: is brute-force avoidable?, Genus distribution of $P_3 \mathop\square P_n$, Treewidth lower bounds with brambles, Practical algorithms for MSO model-checking on tree-decomposable graphs, An annotated bibliography on guaranteed graph searching, Patterns with bounded treewidth, Approximation algorithms for digraph width parameters, On the bend-number of planar and outerplanar graphs, On triangulating $k$-outerplanar graphs, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, The degree-diameter problem for sparse graph classes, The complexity of minimum-length path decompositions, On the parameterized complexity of non-monotonic logics, 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, Linear-time algorithm for sliding tokens on trees, Complexity of rainbow vertex connectivity problems for restricted graph classes, The behavior of clique-width under graph operations and graph transformations, Improved algorithms and complexity results for power domination in graphs, Pebbling in semi-2-trees, On making a distinguished vertex of minimum degree by vertex deletion, A note on exact algorithms for vertex ordering problems on graphs, Treewidth computations. I: Upper bounds, Spanning tree congestion of $k$-outerplanar graphs, Computing branchwidth via efficient triangulations and blocks, On the complexity of some subgraph problems, Minimum dominating set of queens: a trivial programming exercise?, Bijective linear time coding and decoding for $k$-trees, Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design, Independence polynomials of $k$-tree related graphs, Monadic second-order model-checking on decomposable matroids, Treewidth computations. II. Lower bounds, On the graph complement conjecture for minimum semidefinite rank, Complexity and approximation of the constrained forest problem, The complexity of counting homomorphisms seen from the other side, Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs, The carving-width of generalized hypercubes, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Restricted space algorithms for isomorphism on bounded treewidth graphs, On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth, Neighbor sum distinguishing total coloring of graphs with bounded treewidth, On the maximum number of cliques in a graph, On the computational complexity of vertex integrity and component order connectivity, Monotony properties of connected visible graph searching, Matrix norms and rapid mixing for spin systems, Lower bounds for treewidth of product graphs, Graphs without large apples and the maximum weight independent set problem, A single-exponential FPT algorithm for the $K_4$-\textsc{minor cover} problem, Approximating the partition function of planar two-state spin systems, On bounded-degree vertex deletion parameterized by treewidth, 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, A Retrospective on (Meta) Kernelization, Fast Algorithms for Join Operations on Tree Decompositions, Tree-decompositions with bags of small diameter, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, Complexity and Polynomially Solvable Special Cases of QUBO, Multi-classifiers of Small Treewidth, A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity, Fixed-Parameter Tractability of Treewidth and Pathwidth, Constructing Brambles, Graph drawings with few slopes, Approximation of the Quadratic Knapsack Problem, The relative clique-width of a graph, Treewidth computation and extremal combinatorics, Computing optimal Steiner trees in polynomial space, On Compiling Structured CNFs to OBDDs, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Sparse Graphs of High Gonality, Boundary classes for graph problems involving non-local properties, Exact square coloring of subcubic planar graphs, Definability equals recognizability for $k$-outerplanar graphs and $l$-chordal partial $k$-trees, A Turing kernelization dichotomy for structural parameterizations of $\mathcal{F} $-minor-free deletion, The $k$-strong induced arboricity of a graph, On the vertex cover $P_3$ problem parameterized by treewidth, On compiling structured CNFs to OBDDs, Gallai's conjecture for graphs with treewidth 3, From tree-decompositions to clique-width terms, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, A Note on the Minimum H-Subgraph Edge Deletion, On a characterization of k-trees, On the computational complexity of the bipartizing matching problem, Large Induced Subgraphs via Triangulations and CMSO, Low Polynomial Exclusion of Planar Graph Patterns, Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem, Complexity and Approximation Results for the Connected Vertex Cover Problem, Pathwidth of Circular-Arc Graphs, On strict brambles, Sharp separation and applications to exact and parameterized algorithms, Domination and convexity problems in the target set selection model, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Unnamed Item, Scheduling of pipelined operator graphs, Sublinear-space approximation algorithms for Max $r$-SAT, The inverse inertia problem for the complements of partial $k$-trees, Relating the annihilation number and the total domination number for some graphs, On treewidth, separators and Yao's garbling, A Characterization of the degree sequences of 2-trees, Fractals for Kernelization Lower Bounds, On computing the Hamiltonian index of graphs, Reconfiguration of cliques in a graph, Parameters Tied to Treewidth, Obstructions for linear rank-width at most 1, Digraph width measures in parameterized algorithmics, Characterizing graphs of small carving-width, EPG-representations with Small Grid-Size, Faster Steiner Tree Computation in Polynomial-Space, Solving Graph Problems via Potential Maximal Cliques, Vertex-minor reductions can simulate edge contractions, Algorithms for finding distance-edge-colorings of graphs, Orthogonal Tree Decompositions of Graphs, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Solving \#SAT using vertex covers, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$, Satisfiability of Acyclic and almost Acyclic CNF Formulas (II), Tree decompositions of graphs: saving memory in dynamic programming, How to Cut a Graph into Many Pieces, Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph, Lower bounds on the pathwidth of some grid-like graphs, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, The Maximum Independent Set Problem in Planar Graphs, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, Linear layouts measuring neighbourhoods in graphs, Fixed-parameter tractability results for full-degree spanning tree and its dual, Complexity Results for the Spanning Tree Congestion Problem, A Quartic Kernel for Pathwidth-One Vertex Deletion, A $c^k n$ 5-Approximation Algorithm for Treewidth, Completely independent spanning trees in (partial) $k$-trees, A Local Search Algorithm for Branchwidth, Equitable list coloring and treewidth, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Bidimensionality and Kernels, Upper Domination: Complexity and Approximation, Algebraic Complexity Classes, Triangulation Heuristics for BN2O Networks, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Exploring the Subexponential Complexity of Completion Problems, FPT is characterized by useful obstruction sets, Dynamic algorithms for graphs of bounded treewidth, Kernelization: New Upper and Lower Bound Techniques, Cycle decompositions and constructive characterizations, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs, Graph decompositions for cartesian products

Cites Work