A hard problem that is almost always easy

DOI10.1007/BFB0015426MaRDI QIDQ6487965zbMATH OpenFDO

Authors 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)

Recommendations

• An Average Case NP-complete Graph Colouring Problem
• scientific article; zbMATH DE number 1072538
• The solution of some random NP-hard problems in polynomial expected time
• Average polynomial time complexity of some NP-complete problems
• scientific article; zbMATH DE number 1008518

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 799777 (Why is no real title available?)
• Algorithm and bound for the greatest common divisor of n integers
• Average Case Complete Problems
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Determining the Chromatic Number of a Graph
• Determining the Stability Number of a Graph
• Hard Knapsack Problems
• Input-output decomposition of dynamic systems is NP-complete
• On the Computational Complexity of Combinatorial Problems
• The NP-completeness column: An ongoing guide

Cited in

(6)

• Average polynomial time complexity of some NP-complete problems
• On percolation and NP-hardness
• On percolation and \(\mathcal{NP}\)-hardness
• An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 436075 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487965)