A hard problem that is almost always easy

DOI10.1007/BFB0015426MaRDI QIDQ6487965zbMATH OpenFDO

Authors George Havas, Bohdan S. Majewski

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015426

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(8)

• Average polynomial time complexity of some NP-complete problems
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 999544 (Why is no real title available?)
• scientific article; zbMATH DE number 436075 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• 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\))

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)