# A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set

1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The Lexicographically First Maximal Independent Set Problem'' on graphs with bounded degree 3 is at most sqrt(n)-complete, and thus very likely not parallelizable in a fine-grained setting. On the other hand, we show that in a coarse-grained setting (few processors and a lot of data) the situation is different, by giving a work-optimal algorithm on a shared memory machine for n and p such that p log p \in O(\log n).
Mots-clés :
Type de document :
Communication dans un congrès
Blundo, Carlo and Laneve, Cosimo. Italian Conference on Theoretical Computer Science - ICTCS'03, Oct 2003, Bertinoro, Italy, Springer, 2841, pp.125-136, 2003, Lecture Notes in Computer Science. 〈10.1007/b13810〉
Domaine :

https://hal.inria.fr/inria-00099545
Contributeur : Jens Gustedt <>
Soumis le : mardi 26 septembre 2006 - 09:38:28
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

### Citation

Jens Gustedt, Jan Arne Telle. A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set. Blundo, Carlo and Laneve, Cosimo. Italian Conference on Theoretical Computer Science - ICTCS'03, Oct 2003, Bertinoro, Italy, Springer, 2841, pp.125-136, 2003, Lecture Notes in Computer Science. 〈10.1007/b13810〉. 〈inria-00099545〉

### Métriques

Consultations de la notice