Average polynomial time complexity of some NP-complete problems
- 31 December 1986
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 46, 219-237
- https://doi.org/10.1016/0304-3975(86)90031-9
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- On the average number of steps of the simplex method of linear programmingMathematical Programming, 1983
- The Worst and the Most Probable Performance of a Class of Set-Covering AlgorithmsSIAM Journal on Computing, 1983
- A probabilistic analysis of a new satisfiability algorithmRAIRO. Informatique théorique, 1982
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete ProblemsSIAM Journal on Computing, 1981
- Finding a Maximum Independent SetSIAM Journal on Computing, 1977
- A New Algorithm for Generating All the Maximal Independent SetsSIAM Journal on Computing, 1977
- Asymptotical estimation of some characteristics of finite graphsRAIRO. Informatique théorique, 1977