LP can be a cure for parameterized problems
From MaRDI portal
Recommendations
- Faster parameterized algorithms using linear programming
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Improved Parameterized Upper Bounds for Vertex Cover
Cited in
(26)- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- Above guarantee parameterization for vertex cover on graphs with maximum degree 4
- Faster graph bipartization
- Half-integrality, LP-branching, and FPT algorithms
- Generalized above guarantee vertex cover and r-partization
- Parameterized approximations via d-skew-symmetric multicut
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Designing FPT algorithms for cut problems using randomized contractions
- Solving min ones 2-SAT as fast as vertex cover
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- LP-branching algorithms based on biased graphs
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- Faster parameterized algorithms using linear programming
- New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
- Rank vertex cover as a natural problem for algebraic compression
- Linear-time FPT algorithms via network flow
- Half-integrality, LP-branching and FPT algorithms
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- Reducing the vertex cover number via edge contractions
- What Is Known About Vertex Cover Kernelization?
- On the parallel parameterized complexity of MaxSAT variants
- Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs
- Kernelization in almost linear time for clustering into bounded vertex cover components
- Complexity of local search for CSPs parameterized by constraint difference
- On the parameterized vertex cover problem for graphs with perfect matching
- Data reductions and combinatorial bounds for improved approximation algorithms
This page was built for publication: LP can be a cure for parameterized problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904774)
