Parallel Search for Maximal Independence Given Minimal Dependence
| Title | Parallel Search for Maximal Independence Given Minimal Dependence |
| Publication Type | Technical Report |
| Year of Publication | 1989 |
| Authors | Beame, P., & Luby M. |
| Other Numbers | 502 |
| 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. |
| URL | http://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 |