What Is Known About Vertex Cover Kernelization?
From MaRDI portal
Publication:6163635
DOI10.1007/978-3-319-98355-4_19zbMath1514.68213arXiv1811.09429OpenAlexW2886237949MaRDI QIDQ6163635
Frances A. Rosamond, Michael R. Fellows, Lars Jaffke, Unnamed Author, Mathias Weller
Publication date: 30 June 2023
Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.09429
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (max. 100)
Collaborating with Hans: Some Remaining Wonderments ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Disentangling the computational complexity of network untangling ⋮ Reflections on kernelizing and computing unrooted agreement forests
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Lower bounds on kernelization
- A kernel of order \(2k - c\) for Vertex Cover
- Heuristic algorithms in computational molecular biology
- Advice classes of parametrized tractability
- Improved upper bounds for vertex cover
- Parameterized algorithm for eternal vertex cover
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- A kernel of order \(2k-c\log k\) for vertex cover
- Parameterized complexity of Vertex Cover variants
- Clique-detection models in computational biochemistry and genomics
- Vertex Cover: Further Observations and Further Improvements
- Kernelization – Preprocessing with a Guarantee
- Efficient Classification for Metric Data
- Vertex Cover Structural Parameterization Revisited
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- On Problems without Polynomial Kernels (Extended Abstract)
- Nondeterminism within $P^ * $
- Properties of vertex packing and independence system polyhedra
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- Parameterized and Exact Computation
- Optimal Protein Structure Alignment Using Maximum Cliques
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- On the complexity of \(k\)-SAT
This page was built for publication: What Is Known About Vertex Cover Kernelization?
