A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

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

Jens Gustedt
Jan Arne Telle
  • Fonction : Auteur
  • PersonId : 889063

Résumé

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).

Dates et versions

inria-00099545 , version 1 (26-09-2006)

Identifiants

Citer

Jens Gustedt, Jan Arne Telle. A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set. Italian Conference on Theoretical Computer Science - ICTCS'03, EATCS, Oct 2003, Bertinoro, Italy, pp.125-136, ⟨10.1007/b13810⟩. ⟨inria-00099545⟩
32 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More