Solving min ones 2-SAT as fast as vertex cover
From MaRDI portal
Publication:393120
DOI10.1016/j.tcs.2013.07.019zbMath1301.68163OpenAlexW2043560626MaRDI QIDQ393120
Neeldhara Misra, Venkatesh Raman, N. S. Narayanaswamy, Bal Sri Shankar
Publication date: 16 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.019
Related Items (4)
Parameterized complexity of \(d\)-hitting set with quotas ⋮ Neighborhood persistency of the linear optimization relaxation of integer linear optimization ⋮ On the parameterized complexity of reconfiguration problems ⋮ Conflict free version of covering problems on graphs: classical and parameterized
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved upper bounds for vertex cover
- A bounded approximation for the minimum cost 2-sat problem
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- A kernel of order \(2k-c\log k\) for vertex cover
- Fast algorithms for max independent set
- On Multiway Cut Parameterized above Lower Bounds
- Paths, Flowers and Vertex Cover
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Preprocessing of Min Ones Problems: A Dichotomy
- Kernelization Algorithms for d-Hitting Set Problems
- Two Edge Modification Problems without Polynomial Kernels
- Algorithms for maximum independent sets
- Vertex packings: Structural properties and algorithms
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- On efficient fixed-parameter algorithms for weighted vertex cover
- Improved Fixed-Parameter Algorithm for the Minimum Weight 3-SAT Problem
- Representative Sets and Irrelevant Vertices
- Spectral Theory and Analysis
This page was built for publication: Solving min ones 2-SAT as fast as vertex cover
