• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
demetrescu.PDF (394.8Kb)
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
http://dx.doi.org/10.1007/978-3-540-74456-6_19
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

Related items

Showing items related by title and author.

  • Thumbnail
    Adapting parallel algorithms to the W-Stream model, with applications to graph problems 
    Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil; Ribichini, Andrea (2011) Article accepté pour publication ou publié
  • Thumbnail
    Parallel Algorithms are Good for Streaming 
    Demetrescu, Camil; Escoffier, Bruno; Moruz, Gabriel; Ribichini, Andrea (2006) Document de travail / Working paper
  • Thumbnail
    Algorithmes à véracité garantie pour des problèmes de b‐couplage dans un graphe biparti 
    Escoffier, Bruno; Monnot, Jérôme; Pascual, Fanny; Spanjaard, Olivier (2013) Communication / Conférence
  • Thumbnail
    Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows 
    Cazenave, Tristan; Teytaud, Fabien (2012) Communication / Conférence
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo