A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set
Identifieur interne : 007F87 ( Main/Merge ); précédent : 007F86; suivant : 007F88A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set
Auteurs : Jens Gustedt [France] ; Jan Arne Telle [Norvège]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 2003.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
The Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 is at most 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 E O(log n).
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000687
- to stream PascalFrancis, to step Curation: 000354
- to stream PascalFrancis, to step Checkpoint: 000728
Links to Exploration step
Pascal:04-0212566Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set</title><author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA & INRIA Lorraine</s1><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>LORIA & INRIA Lorraine</wicri:noRegion><wicri:noRegion>LORIA & INRIA Lorraine</wicri:noRegion></affiliation></author><author><name sortKey="Telle, Jan Arne" sort="Telle, Jan Arne" uniqKey="Telle J" first="Jan Arne" last="Telle">Jan Arne Telle</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University of Bergen</s1><s2>Bergen</s2><s3>NOR</s3><sZ>2 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>University of Bergen</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">04-0212566</idno><date when="2003">2003</date><idno type="stanalyst">PASCAL 04-0212566 INIST</idno><idno type="RBID">Pascal:04-0212566</idno><idno type="wicri:Area/PascalFrancis/Corpus">000687</idno><idno type="wicri:Area/PascalFrancis/Curation">000354</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000728</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000728</idno><idno type="wicri:doubleKey">0302-9743:2003:Gustedt J:a:work:optimal</idno><idno type="wicri:Area/Main/Merge">007F87</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set</title><author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA & INRIA Lorraine</s1><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>LORIA & INRIA Lorraine</wicri:noRegion><wicri:noRegion>LORIA & INRIA Lorraine</wicri:noRegion></affiliation></author><author><name sortKey="Telle, Jan Arne" sort="Telle, Jan Arne" uniqKey="Telle J" first="Jan Arne" last="Telle">Jan Arne Telle</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University of Bergen</s1><s2>Bergen</s2><s3>NOR</s3><sZ>2 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>University of Bergen</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="2003">2003</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Coarse grain structure</term><term>Computer theory</term><term>Graph degree</term><term>Independent graph</term><term>Independent set</term><term>Maximal graph</term><term>Optimal algorithm</term><term>Shared memory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Algorithme optimal</term><term>Mémoire partagée</term><term>Structure gros grain</term><term>Ensemble indépendant</term><term>Graphe maximal</term><term>Degré graphe</term><term>Graphe indépendant</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 is at most 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 E O(log n).</div></front></TEI><affiliations><list><country><li>France</li><li>Norvège</li></country></list><tree><country name="France"><noRegion><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name></noRegion></country><country name="Norvège"><noRegion><name sortKey="Telle, Jan Arne" sort="Telle, Jan Arne" uniqKey="Telle J" first="Jan Arne" last="Telle">Jan Arne Telle</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007F87 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 007F87 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:04-0212566
|texte= A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set
}}
| This area was generated with Dilib version V0.6.33. |  |