LP can be a cure for parameterized problems

DOI10.4230/LIPICS.STACS.2012.338MaRDI QIDQ2904774zbMATH OpenFDO

Authors N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh

Publication date 23 August 2012

zbMATH Keywords

graph algorithmsvertex coverparameterized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

(23)

• Solving min ones 2-SAT as fast as vertex cover
• Faster parameterized algorithms using linear programming
• Designing FPT algorithms for cut problems using randomized contractions
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• Parameterized approximations via \(d\)-skew-symmetric multicut
• Reducing the vertex cover number via edge contractions
• On the parallel parameterized complexity of MaxSAT variants
• On the parameterized vertex cover problem for graphs with perfect matching
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Rank vertex cover as a natural problem for algebraic compression
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Linear-time FPT algorithms via network flow
• Half-integrality, LP-branching and FPT algorithms
• What Is Known About Vertex Cover Kernelization?
• Data reductions and combinatorial bounds for improved approximation algorithms
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Half-integrality, LP-branching, and FPT algorithms
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Generalized above guarantee vertex cover and r-partization
• LP-branching algorithms based on biased graphs
• Parameterized algorithms and complexity for the traveling purchaser problem and its variants
• Faster graph bipartization

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)