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

DOI10.1007/978-3-642-15155-2_48zbMATH Open1287.68079OpenAlexW1604371039MaRDI QIDQ3586112FDOQ3586112

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

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

Mathematics Subject Classification ID

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

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)