Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
From MaRDI portal
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- A tight Erdős-Pósa function for planar minors
- Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday
- Elimination distances, blocking sets, and kernels for Vertex Cover
- Fundamentals of parameterized complexity
- Graph isomorphism parameterized by elimination distance to bounded degree
- Graph minors. V. Excluding a planar graph
- Graph minors. XX: Wagner's conjecture
- Hitting forbidden minors: approximation and kernelization
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Kernelization -- preprocessing with a guarantee
- Kernelization. Theory of parameterized preprocessing
- On space efficiency of algorithms working on structural decompositions of graphs
- On the hardness of losing width
- Parameterized algorithms
- Parametrized complexity theory.
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Representative sets and irrelevant vertices: new tools for kernelization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Smaller parameters for vertex cover kernelization
- Sparsity. Graphs, structures, and algorithms
- The Erdős-Pósa property for odd cycles in highly connected graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
- Vertex packings: Structural properties and algorithms
- Width, depth, and space: tradeoffs between branching and dynamic programming
Cited in
(3)
This page was built for publication: Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842562)
