Average polynomial time complexity of some NP-complete problems

DOI10.1016/0304-3975(86)90031-9MaRDI QIDQ1091815zbMATH OpenOpenAlexFDO

Authors Phan Dinh Dieu, Le Cong Thanh, Le Tuan Hoa

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90031-9

zbMATH Keywords

NP-complete problemRandom graphsaverage polynomial timeCLIQUE problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A hard problem that is almost always easy
• The solution of some random NP-hard problems in polynomial expected time
• The monotone complexity of \(k\)-clique on random graphs
• An Average Case NP-complete Graph Colouring Problem
• On the average-case complexity of parameterized clique

Cites work

• scientific article; zbMATH DE number 3690716 (Why is no real title available?)
• scientific article; zbMATH DE number 3770947 (Why is no real title available?)
• scientific article; zbMATH DE number 3480503 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3568580 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 3590325 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Asymptotic estimations of certain parameters of finite graphs and their applications
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Finding a Maximum Independent Set
• On colouring random graphs
• On the average number of steps of the simplex method of linear programming
• The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms

Cited in

(9)

• A hard problem that is almost always easy
• On the average-case complexity of parameterized clique
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 436075 (Why is no real title available?)
• On the average complexity of the $k$-level
• Sets computable in polynomial time on average
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• Polynomial-average-time satisfiability problems
• Average case completeness

This page was built for publication: Average polynomial time complexity of some NP-complete problems

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