Exact Algorithms for NP-Hard Problems: A Survey

2003/01/01 by Gerhard J. Woeginger · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Boolean satisfiability problem #Complexity and Algorithms in Graphs #Computer science #Graph #Graph coloring #Knapsack problem #Mathematical optimization #Mathematics #Satisfiability #Scheduling (production processes) #Theoretical computer science #Travelling salesman problem #Vehicle Routing Optimization Methods

paper · doi:10.1007/3-540-36478-1_17

crossref issued 2003/01/01 · crossref published 2003/01/01 · crossref published-print 2003/01/01 · openalex publication_date 2003/01/01 · crossref published-online 2003/01/30 · crossref created 2007/10/20 · crossref deposited 2025/01/21 · openalex created_date 2025/10/10 · crossref indexed 2026/07/01 · openalex updated_date 2026/08/01

Citations

• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• A note on the complexity of the chromatic number problem
• On cliques in graphs
• Optimization, approximation, and complexity classes
• Computing Partitions with Applications to the Knapsack Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Minimizing the Number of States in Incompletely Specified Sequential Switching Functions
• A probabilistic algorithm for k-SAT and constraint satisfaction problems
• Complexity of k-SAT

Cited by

• The Complexity of Euclidian 2 Dimension Travelling Salesman Problem versus General Assign Problem, NP is not P
• Computational hardness assumption [wikipedia]