Thumbnail

Adapting parallel algorithms to the W-Stream model, with applications to graph problems

Ribichini, Andrea; Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil (2007), Adapting parallel algorithms to the W-Stream model, with applications to graph problems, in Kucera, Ludek; Kucera, Antonin, Mathematical Foundations of Computer Science 2007 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, Springer : Berlin, p. 194-205. http://dx.doi.org/10.1007/978-3-540-74456-6_19

View/Open
Type
Communication / Conférence
Date
2007
Conference title
32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)
Conference date
2007-08
Conference city
Ceský Krumlov
Conference country
République tchèque
Book title
Mathematical Foundations of Computer Science 2007 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings
Book author
Kucera, Ludek; Kucera, Antonin
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4708
Published in
Berlin
ISBN
978-3-540-74455-9
Number of pages
764
Pages
194-205
Publication identifier
Metadata
Show full item record
Author(s)
Ribichini, Andrea
Moruz, Gabriel
Escoffier, Bruno
Demetrescu, Camil
Abstract (EN)
In 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.
Subjects / Keywords
Graph problems; Reductions to parallel algorithms; Data streaming model