@conference {17599,
title = {Finding large independent sets of hypergraphs in parallel},
booktitle = {Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures},
series = {SPAA {\textquoteright}01},
year = {2001},
month = {2001///},
pages = {163 - 168},
publisher = {ACM},
organization = {ACM},
address = {New York, NY, USA},
abstract = {A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound \&agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size \&agr;k (H). They also show that \&agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size \&agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.},
keywords = {hypergraphs, independent sets, Parallel algorithms, randomized algorithms},
isbn = {1-58113-409-6},
doi = {10.1145/378580.378622},
url = {http://doi.acm.org/10.1145/378580.378622},
author = {Shachnai,Hadas and Srinivasan, Aravind}
}