Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel (Q5048303): Difference between revisions

Latest revision as of 19:51, 30 July 2024

scientific article; zbMATH DE number 7617249

Language	Label	Description	Also known as
English	Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel	scientific article; zbMATH DE number 7617249

Statements

instance of

scholarly article

0 references

title

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel (English)

0 references

0 references

0 references

0 references

SIAM Journal on Discrete Mathematics

0 references

publication date

15 November 2022

0 references

full work available at URL

https://arxiv.org/abs/2004.12865

0 references

zbMATH Keywords

vertex cover

0 references

parameterized complexity

0 references

polynomial kernel

0 references

structural parameterization

0 references

bridge-depth

0 references

describes a project that uses

Algorithm 447

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?

0 references

Graph isomorphism parameterized by elimination distance to bounded degree

0 references

Width, depth, and space: tradeoffs between branching and dynamic programming

0 references

Parameterized Algorithms

0 references

On the hardness of losing width

0 references

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

0 references

Fundamentals of parameterized complexity

0 references

What Is Known About Vertex Cover Kernelization?

0 references

Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity

0 references

Parametrized complexity theory.

0 references

Hitting Forbidden Minors: Approximation and Kernelization

0 references

Kernelization

0 references

Vertex Cover Structural Parameterization Revisited

0 references

Smaller Parameters for Vertex Cover Kernelization

0 references

Elimination distances, blocking sets, and kernels for Vertex Cover

0 references

Q3113682

0 references

Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

0 references

Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.

0 references

A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter

0 references

Kernelization – Preprocessing with a Guarantee

0 references

Polynomial kernels for vertex cover parameterized by small degree modulators

0 references

Vertex packings: Structural properties and algorithms

0 references

Tree-depth, subgraph coloring and homomorphism bounds

0 references

Sparsity. Graphs, structures, and algorithms

0 references

Q5710169

0 references

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs

0 references

The Erdős-Pósa property for odd cycles in highly connected graphs

0 references

Graph minors. V. Excluding a planar graph

0 references

Graph minors. XX: Wagner's conjecture

0 references

A tight Erdős-Pósa function for planar minors

0 references

Identifiers

zbMATH Open document ID

1503.05095

0 references

DOI

10.1137/21M1400766

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5048303

@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
+Normal rank
@@ Property / cites work @@
+Graph isomorphism parameterized by elimination distance to bounded degree
+Normal rank
@@ Property / cites work @@
+Width, depth, and space: tradeoffs between branching and dynamic programming
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of losing width
@@ Property / cites work: On the hardness of losing width / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / rank @@
+Normal rank
@@ Property / cites work @@
+What Is Known About Vertex Cover Kernelization?
@@ Property / cites work: What Is Known About Vertex Cover Kernelization? / rank @@
+Normal rank
@@ Property / cites work @@
+Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+Hitting Forbidden Minors: Approximation and Kernelization
+Normal rank
@@ Property / cites work @@
+Kernelization
@@ Property / cites work: Kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex Cover Structural Parameterization Revisited
+Normal rank
@@ Property / cites work @@
+Smaller Parameters for Vertex Cover Kernelization
@@ Property / cites work: Smaller Parameters for Vertex Cover Kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+Elimination distances, blocking sets, and kernels for Vertex Cover
+Normal rank
@@ Property / cites work @@
+Q3113682
@@ Property / cites work: Q3113682 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
+Normal rank
@@ Property / cites work @@
+Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
+Normal rank
@@ Property / cites work @@
+A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
+Normal rank
@@ Property / cites work @@
+Kernelization – Preprocessing with a Guarantee
@@ Property / cites work: Kernelization – Preprocessing with a Guarantee / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial kernels for vertex cover parameterized by small degree modulators
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Tree-depth, subgraph coloring and homomorphism bounds
+Normal rank
@@ Property / cites work @@
+Sparsity. Graphs, structures, and algorithms
@@ Property / cites work: Sparsity. Graphs, structures, and algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
+Normal rank
@@ Property / cites work @@
+The Erdős-Pósa property for odd cycles in highly connected graphs
+Normal rank
@@ Property / cites work @@
+Graph minors. V. Excluding a planar graph
@@ Property / cites work: Graph minors. V. Excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. XX: Wagner's conjecture
@@ Property / cites work: Graph minors. XX: Wagner's conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+A tight Erdős-Pósa function for planar minors
@@ Property / cites work: A tight Erdős-Pósa function for planar minors / rank @@
+Normal rank