Sparse obstructions for minor-covering parameters
DOI10.1016/J.DAM.2019.10.021zbMATH Open1437.05219OpenAlexW2986444897WikidataQ126852321 ScholiaQ126852321MaRDI QIDQ2174553FDOQ2174553
Authors: Dimitris Chatzidimitriou, Dimitrios M. Thilikos, Dimitris Zoros 
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
Recommendations
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Improved sparse covers for graphs excluding a fixed minor
- scientific article; zbMATH DE number 176214
- Extremal density for sparse minors and subdivisions
- scientific article; zbMATH DE number 5583574
- Extremal functions for sparse minors
- On computing graph minor obstruction sets
- Minimal covers and filter spaces
- Minimal obstructions for partial representations of interval graphs
- Minimal obstructions for partial representations of interval graphs
graph minorsobstruction setsfinite integer indextree decompositionsapex-extensionsprotrusion decompositions
Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)
Cites Work
- Fundamentals of parameterized complexity
- Properties of vertex packing and independence system polyhedra
- Graph minors. XX: Wagner's conjecture
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Parameterized algorithms
- Title not available (Why is that?)
- 103 graphs that are irreducible for the projective plane
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- A kuratowski theorem for the projective plane
- Bidimensionality and kernels
- Treewidth. Computations and approximations
- Polynomial bounds for the grid-minor theorem
- Excluded-minor characterization of apex-outerplanar graphs
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Obstruction set isolation for the gate matrix layout problem
- Algorithms and obstructions for linear-width and related search parameters
- Contraction obstructions for connected graph searching
- Excluded grid theorem: improved and simplified
- The obstructions for toroidal graphs with no \(K_{3,3}\)'s
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Obstructions of connectivity two for embedding graphs into the torus
- Properties of vertex cover obstructions
- The Structure and Number of Obstructions to Treewidth
- Minor‐order obstructions for the graphs of vertex cover 6
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Title not available (Why is that?)
- Forbidden graphs for tree-depth
- Forbidden minors characterization of partial 3-trees
- Title not available (Why is that?)
- Outerplanar obstructions for matroid pathwidth
- Outerplanar obstructions for the feedback vertex set
- Title not available (Why is that?)
- Title not available (Why is that?)
- Forbidden minors to graphs with small feedback sets
- The structure of obstructions to treewidth and pathwidth
- Reduction algorithms for graphs of small treewidth
- Title not available (Why is that?)
- A Menger-like property of tree-width: The finite case
- Upper bounds on the size of obstructions and intertwines
- Title not available (Why is that?)
- (Meta) kernelization
- Data-compression for parametrized counting problems on sparse graphs
- Graphs with Branchwidth at Most Three
- FPT is characterized by useful obstruction sets
- Cutwidth: obstructions and algorithmic aspects
Cited In (5)
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Faster parameterized algorithms for modification problems to minor-closed classes
- Achievable sets, brambles, and sparse treewidth obstructions
- Title not available (Why is that?)
- Improved sparse covers for graphs excluding a fixed minor
This page was built for publication: Sparse obstructions for minor-covering parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174553)
