Average polynomial time complexity of some NP-complete problems

DOI10.1016/0304-3975(86)90031-9zbMath0623.68039OpenAlexW2062731608MaRDI QIDQ1091815

Le Cong Thanh, Phan Dinh Dieu, Lê Tuân 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

average polynomial timeNP-complete problemRandom graphsCLIQUE problem

Mathematics Subject Classification ID

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

Related Items

Average case completeness

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Asymptotic estimations of certain parameters of finite graphs and their applications
• 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
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• On colouring random graphs
• Finding a Maximum Independent Set
• A New Algorithm for Generating All the Maximal Independent Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item