A hard problem that is almost always easy

DOI10.1007/BFB0015426zbMATH Open1512.68109MaRDI QIDQ6487965FDOQ6487965

Authors: George Havas, Bohdan S. Majewski 

Publication date: 21 March 2023

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)