Faster exact solutions for some NP-hard problems.

DOI10.1016/S0304-3975(01)00257-2zbMath1061.68060MaRDI QIDQ1853491

David Peleg, Limor Drori

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Partition into triangles on bounded degree graphs ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ New algorithms for exact satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• On space-efficient algorithms for certain NP-complete problems
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Finding a Maximum Independent Set
• The complexity of satisfiability problems

This page was built for publication: Faster exact solutions for some NP-hard problems.