Average polynomial time complexity of some NP-complete problems
type: Item
instance of: scholarly article
title: Average polynomial time complexity of some NP-complete problems
zbMATH Open document ID: 0623.68039
DOI: 10.1016/0304-3975(86)90031-9
author: Phan Dinh Dieu
author: Le Cong Thanh
author: Le Tuan Hoa
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Random graphs with n vertices are considered such that any edge occurs independently swith the same probability p. It is proved that the CLIQUE problem can be solved in average polynomial time for these graphs when \(p=n^{-\epsilon}\), where \(\epsilon >0\) is a constant. Besides, the problem CLIQUE(N(n)) is considered for the graphs with a number of edges less than N(n). It is shown that this problem can also be solved in average polynomial time for any function \(0\leq N(n)\leq n^{2-\epsilon}\), where \(0<\epsilon <2\). Provided that \(N(n)\geq n^{\epsilon}\), the latter problem is NP-complete.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 4011930
zbMATH Keywords: NP-complete problem
zbMATH Keywords: Random graphs
zbMATH Keywords: CLIQUE problem
zbMATH Keywords: average polynomial time
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90031-9
OpenAlex ID: W2062731608
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Q3951539
cites work: Q4065548
cites work: Q4198056
cites work: On colouring random graphs
cites work: Q4144785
cites work: The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms
cites work: Q4141146
cites work: Asymptotic estimations of certain parameters of finite graphs and their applications
cites work: Q4063075
cites work: Q4159413
cites work: Q3885209
cites work: A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
cites work: On the average number of steps of the simplex method of linear programming
cites work: Finding a Maximum Independent Set
cites work: A New Algorithm for Generating All the Maximal Independent Sets
description: scientific article; zbMATH DE number 4011930