登入
選單
返回
Google圖書搜尋
On the Expected Performance of a Parallel Algorithm for Finding Maximal Independent Subsets of a Random Graph
Neil J. Calkin
Alan Frieze
L. Kucera
出版
Carnegie Mellon University, Department of Mathematics
, 1991
URL
http://books.google.com.hk/books?id=TwFEtwAACAAJ&hl=&source=gbs_api
註釋
Abstract: "We consider the parallel greedy algorithm of Coppersmith, Raghavan and Tompa [CRT] for finding the lexicographically first maximal independent set of a graph. We prove an [omega](log n) bound on the expected number if [sic] iterations for most edge densities. This complements the O(log n) bound proved in Calkin and Frieze [CF]."
