Solving \textsc{minones-2-sat} as fast as \textsc{vertex cover}

DOI10.1007/978-3-642-15155-2_48MaRDI QIDQ3586112zbMATH OpenOpenAlexFDO

Authors Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, Bal Sri Shankar

Publication date 3 September 2010

Published in Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15155-2_48

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Solving min ones 2-SAT as fast as vertex cover
• On approximation algorithms for the minimum satisfiability problem
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• Mathematical Foundations of Computer Science 2004
• Approximating MIN 2-SAT and MIN 3-SAT

Cited in

(2)

• Solving min ones 2-SAT as fast as vertex cover
• Clause-connected versions of the satisfiability problem

This page was built for publication: Solving \textsc{minones-2-sat} as fast as \textsc{vertex cover}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586112)