Parallel Search for Maximal Independence Given Minimal Dependence

TitleParallel Search for Maximal Independence Given Minimal Dependence
Publication TypeTechnical Report
Year of Publication1989
AuthorsBeame, P., & Luby M.
Other Numbers502
Abstract

We consider the problem of finding a maximal independent set fast in parallel when the independence system is presented as an explicit list of minimal dependent sets. Karp and Wigderson [KW] were the first to find an NC algorithm for the special case when the size of each minimal dependent set is at most two, and subsequent work by Luby [Lu1], by Alon, Babai and Itai[ABI] and Goldberg and Spencer [GS] have introduced substantially better algorithms for this case. On the other hand, no previous work on this problem extends even to the case when the size of each minimal dependent set is at most a constant, and we conjecture that this algorithm is a randomized NC algorithm for the general case.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-003.pdf
Bibliographic Notes

ICSI Technical Report TR-89-003

Abbreviated Authors

P. Beame and M. Luby

ICSI Publication Type

Technical Report