Show simple item record

dc.contributor.authorRibichini, Andrea
dc.contributor.authorMoruz, Gabriel
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorDemetrescu, Camil
dc.date.accessioned2011-03-22T14:36:23Z
dc.date.available2011-03-22T14:36:23Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5795
dc.language.isoenen
dc.subjectGraph problemsen
dc.subjectReductions to parallel algorithmsen
dc.subjectData streaming model
dc.subject.ddc003en
dc.titleAdapting parallel algorithms to the W-Stream model, with applications to graph problemsen
dc.typeCommunication / Conférence
dc.description.abstractenIn this paper we show how parallel algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the W − Stream . In this model, at each pass one input stream is read and one output stream is written; streams are pipelined in such a way that the output stream produced at pass i is given as input stream at pass i  + 1. Our techniques give new insights on developing streaming algorithms and yield optimal algorithms (up to polylog factors) for several classical problems in this model including sorting, connectivity, minimum spanning tree, biconnected components, and maximal independent set.en
dc.identifier.citationpages194-205en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4708
dc.relation.ispartoftitleMathematical Foundations of Computer Science 2007 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedingsen
dc.relation.ispartofeditorKucera, Ludek
dc.relation.ispartofeditorKucera, Antonin
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2007
dc.relation.ispartofpages764en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-74456-6en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-74455-9en
dc.relation.conftitle32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)en
dc.relation.confdate2007-08
dc.relation.confcityCeský Krumloven
dc.relation.confcountryRépublique tchèqueen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-74456-6_19


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record