Preprocessing to reduce the search space: antler structures for feedback vertex set
From MaRDI portal
Publication:6564613
DOI10.1016/j.jcss.2024.103532MaRDI QIDQ6564613
Huib Donkers, Bart M. P. Jansen
Publication date: 1 July 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Infeasibility of instance compression and succinct PCPs for NP
- Improved upper bounds for vertex cover
- Center-based clustering under perturbation stability
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- A cubic kernel for feedback vertex set and loop cutset
- Dynamic programming algorithms for the zero-one knapsack problem
- Improved analysis of highest-degree branching for feedback vertex set
- A completeness theory for polynomial (Turing) kernelization
- Recent techniques and results on the Erdős-Pósa property
- Crown structures for vertex cover kernelization
- Parametrized complexity theory.
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- A 4 k 2 kernel for feedback vertex set
- (Meta) Kernelization
- Presolve Reductions in Mixed Integer Programming
- New Limits to Classical and Quantum Instance Compression
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Vertex packings: Structural properties and algorithms
- Color-coding
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Kernelization
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Faster Parameterized Algorithms Using Linear Programming
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- Representative Sets and Irrelevant Vertices
- Mixed Integer Programming: Analyzing 12 Years of Progress
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- The Problem of Simplifying Truth Functions
- The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Preprocessing to reduce the search space: antler structures for feedback vertex set