Local tree-width, excluded minors, and approximation algorithms
From MaRDI portal
Publication:2494422
DOI10.1007/s00493-003-0037-9zbMath1089.05503arXivmath/0001128OpenAlexW2013522700WikidataQ55934709 ScholiaQ55934709MaRDI QIDQ2494422
Publication date: 27 June 2006
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0001128
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Minors and dimension, Layered separators in minor-closed graph classes with applications, Linear kernels for outbranching problems in sparse digraphs, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Local 2-separators, Structure of Graphs with Locally Restricted Crossings, PTAS for Sparse General-valued CSPs, Target set selection with maximum activation time, Parameterized complexity of finding small degree-constrained subgraphs, Approximation of minimum weight spanners for sparse graphs, Approximating sparse quadratic programs, Approximation algorithms via contraction decomposition, Size-treewidth tradeoffs for circuits computing the element distinctness function, Contracting planar graphs to contractions of triangulations, Local search: is brute-force avoidable?, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Guard games on graphs: keep the intruder out!, Implicit branching and parameterized partial cover problems, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Minimal classes of graphs of unbounded clique-width, Orthogonal Tree Decompositions of Graphs, The degree-diameter problem for sparse graph classes, Polynomial bounds for centered colorings on proper minor-closed graph classes, Linearity of grid minors in treewidth with applications through bidimensionality, Parameterized complexity of the spanning tree congestion problem, Unnamed Item, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, Large Independent Sets in Subquartic Planar Graphs, Distributed Dominating Set Approximations beyond Planar Graphs, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, On the complexity of reasoning about opinion diffusion under majority dynamics, 1-planarity testing and embedding: an experimental study, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Unnamed Item, Simple PTAS's for families of graphs excluding a minor
