Local tree-width, excluded minors, and approximation algorithms
From MaRDI portal
Publication:2494422
Abstract: The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph theoretic result is a decomposition theorem for graphs with excluded minors that essentially says that such graphs can be decomposed into trees of graphs of bounded local tree-width. As an application of this theorem, we show that a number of combinatorial optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.
Recommendations
- Improved bounds for the excluded-minor approximation of treedepth
- Improved bounds for the excluded-minor approximation of treedepth
- Dominating sets and local treewidth
- Graph minors. II. Algorithmic aspects of tree-width
- Graph Drawing
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Inapproximability of treewidth and related problems
- On extremal sizes of locally \(k\)-tree graphs.
Cited in
(44)- Parameterized complexity of the spanning tree congestion problem
- Guard games on graphs: keep the intruder out!
- Layered separators in minor-closed graph classes with applications
- Linearity of grid minors in treewidth with applications through bidimensionality
- Improved bounds for the excluded-minor approximation of treedepth
- Minimal classes of graphs of unbounded clique-width
- Approximation algorithms for polynomial-expansion and low-density graphs
- A polynomial excluded-minor approximation of treedepth
- The degree-diameter problem for sparse graph classes
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Orthogonal tree decompositions of graphs
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- scientific article; zbMATH DE number 1947048 (Why is no real title available?)
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Implicit branching and parameterized partial cover problems
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Simple PTAS's for families of graphs excluding a minor
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Parameterized complexity of directed Steiner tree on sparse graphs
- Large independent sets in subquartic planar graphs
- Approximating sparse quadratic programs
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Algorithmic properties of sparse digraphs
- PTAS for Sparse General-valued CSPs
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Approximation of minimum weight spanners for sparse graphs
- Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
- Minors and dimension
- Structure of graphs with locally restricted crossings
- Contracting planar graphs to contractions of triangulations
- Approximation algorithms via contraction decomposition
- Local 2-separators
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Distributed Dominating Set Approximations beyond Planar Graphs
- On the complexity of reasoning about opinion diffusion under majority dynamics
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Linear kernels for outbranching problems in sparse digraphs
- LATIN 2004: Theoretical Informatics
- Target set selection with maximum activation time
- Local search: is brute-force avoidable?
- 1-planarity testing and embedding: an experimental study
- Parameterized complexity of finding small degree-constrained subgraphs
This page was built for publication: Local tree-width, excluded minors, and approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494422)
