Average polynomial time complexity of some NP-complete problems

DOI10.1016/0304-3975(86)90031-9zbMATH Open0623.68039OpenAlexW2062731608MaRDI QIDQ1091815FDOQ1091815

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

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

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)

Cites Work

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

Cited In (9)

• Average case completeness
• Polynomial-average-time satisfiability problems
• On the average complexity of the $k$-level
• Title not available (Why is that?)
• On the average-case complexity of parameterized clique
• Sets computable in polynomial time on average
• A hard problem that is almost always easy
• The solution of some random NP-hard problems in polynomial expected time
• Title not available (Why is that?)

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)