Sparse obstructions for minor-covering parameters
DOI10.1016/j.dam.2019.10.021zbMath1437.05219OpenAlexW2986444897WikidataQ126852321 ScholiaQ126852321MaRDI QIDQ2174553
Dimitris Chatzidimitriou, Dimitris Zoros, Dimitrios M. Thilikos
Publication date: 21 April 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2019.10.021
tree decompositionsgraph minorsobstruction setsfinite integer indexapex-extensionsprotrusion decompositions
Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Density (toughness, etc.) (05C42)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Excluded-minor characterization of apex-outerplanar graphs
- Contraction obstructions for connected graph searching
- Fundamentals of parameterized complexity
- Outerplanar obstructions for matroid pathwidth
- Effective computation of immersion obstructions for unions of graph classes
- Forbidden graphs for tree-depth
- Graph minors. XX: Wagner's conjecture
- Forbidden minors characterization of partial 3-trees
- The obstructions for toroidal graphs with no \(K_{3,3}\)'s
- A Menger-like property of tree-width: The finite case
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- 103 graphs that are irreducible for the projective plane
- Upper bounds on the size of obstructions and intertwines
- Highly connected sets and the excluded grid theorem
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Obstruction set isolation for the gate matrix layout problem
- Quickly excluding a planar graph
- Treewidth. Computations and approximations
- Algorithms and obstructions for linear-width and related search parameters
- The structure of obstructions to treewidth and pathwidth
- Reduction algorithms for graphs of small treewidth
- Properties of vertex cover obstructions
- Parametrized complexity theory.
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Outerplanar Obstructions for the Feedback Vertex Set
- FPT Is Characterized by Useful Obstruction Sets
- Obstructions of Connectivity Two for Embedding Graphs into the Torus
- Excluded Grid Theorem
- The Structure and Number of Obstructions to Treewidth
- (Meta) Kernelization
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- A kuratowski theorem for the projective plane
- Graphs with Branchwidth at Most Three
- Cutwidth: obstructions and algorithmic aspects
- Properties of vertex packing and independence system polyhedra
- Minor‐order obstructions for the graphs of vertex cover 6
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Polynomial bounds for the grid-minor theorem
- Bidimensionality and Geometric Graphs
- Parameterized Algorithms
- Forbidden minors to graphs with small feedback sets
This page was built for publication: Sparse obstructions for minor-covering parameters
