Show simple item record

dc.contributor.authorMoruz, Gabriel
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorDemetrescu, Camil
dc.contributor.authorRibichini, Andrea
dc.date.accessioned2011-03-22T14:41:24Z
dc.date.available2011-03-22T14:41:24Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5796
dc.language.isoenen
dc.subjectData streaming modelen
dc.subjectReductions to parallel algorithmsen
dc.subjectGraph problemsen
dc.subject.ddc003en
dc.titleAdapting parallel algorithms to the W-Stream model, with applications to graph problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper we show how parallel algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the View the MathML source model. In this model, at each pass one input stream is read, one output stream is written, and data items have to be processed using limited space; streams are pipelined in such a way that the output stream produced at pass i is given as input stream at pass i+1. We first introduce a simulation technique that allows turning efficient View the MathML source algorithms into optimal View the MathML source ones, for many classical combinatorial problems, including list ranking and Euler tour of a tree. For other problems, most notably graph problems, however, this technique leads to suboptimal algorithms. To overcome this difficulty we introduce the Relaxed View the MathML source (View the MathML source) computational model, as an intermediate model between View the MathML source and View the MathML source. View the MathML source allows every processor to access a non-constant number of memory cells per parallel round, albeit with some restrictions. The View the MathML source model, while being more powerful than the View the MathML source model, can be simulated in View the MathML source within the same asymptotic bounds. The extra power provided by View the MathML source allows us in many cases to substantially reduce the number of processors, while maintaining the same number of parallel rounds, leading to more efficient View the MathML source simulations of parallel algorithms. Our View the MathML source technique gives new insights on developing streaming algorithms and yields efficient algorithms for several classical problems in this model including sorting, connectivity, minimum spanning tree, biconnected components, and maximal independent set. In addition to allowing smooth space-passes tradeoffs, our algorithms are also shown, by proving almost-tight communication complexity-based lower bounds in View the MathML source, to be optimal up to polylog factors.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol411
dc.relation.isversionofjnlissue44-46
dc.relation.isversionofjnldate2011
dc.relation.isversionofjnlpages3994-4004
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2010.08.030en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record