首页   按字顺浏览 期刊浏览 卷期浏览 Probabilistic analysis of a parallel algorithm for finding maximal independent sets
Probabilistic analysis of a parallel algorithm for finding maximal independent sets

 

作者: Neil Calkin,   Alan Frieze,  

 

期刊: Random Structures&Algorithms  （WILEY Available online 1990）
卷期: Volume 1, issue 1  

页码: 39-50

 

ISSN:1042-9832

 

年代: 1990

 

DOI:10.1002/rsa.3240010104

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

关键词: average case complexity;independent sets;parallel algorithm

 

数据来源: WILEY

 

摘要:

AbstractWe consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphsof arbitrary edge density of O(logn). We prove that conjecture.

 

点击下载:  PDF (354KB)



返 回