A hard problem that is almost always easy

DOI10.1007/BFB0015426zbMath1512.68109MaRDI QIDQ6487965

George Havas, Bohdan S. Majewski

Publication date: 21 March 2023

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Input-output decomposition of dynamic systems is NP-complete
• Average Case Complete Problems
• Hard Knapsack Problems
• On the Computational Complexity of Combinatorial Problems
• Determining the Stability Number of a Graph
• Determining the Chromatic Number of a Graph
• Algorithm and bound for the greatest common divisor of n integers
• The NP-completeness column: An ongoing guide

This page was built for publication: A hard problem that is almost always easy