Faster exact solutions for some NP-hard problems.
From MaRDI portal
Publication:1853491
DOI10.1016/S0304-3975(01)00257-2zbMath1061.68060MaRDI QIDQ1853491
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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(20.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