Publication Details
Title: Parallel Search for Maximal Independence Given Minimal Dependence
Author: P. Beame and M. Luby
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-003.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-003
Bibliographic Reference:
P. Beame and M. Luby. Parallel Search for Maximal Independence Given Minimal Dependence. ICSI Technical Report TR-89-003, February 1989
Author: P. Beame and M. Luby
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-003.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-003
Bibliographic Reference:
P. Beame and M. Luby. Parallel Search for Maximal Independence Given Minimal Dependence. ICSI Technical Report TR-89-003, February 1989