• 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

Parallel Algorithms are Good for Streaming

Demetrescu, Camil; Escoffier, Bruno; Moruz, Gabriel; Ribichini, Andrea (2006), Parallel Algorithms are Good for Streaming. https://basepub.dauphine.fr/handle/123456789/6303

View/Open
cahierLamsade234.pdf (263.4Kb)
Type
Document de travail / Working paper
Date
2006
Publisher
Université Paris-Dauphine
Series title
Cahier du LAMSADE
Series number
234
Published in
Paris
Pages
16
Metadata
Show full item record
Author(s)
Demetrescu, Camil
Escoffier, Bruno
Moruz, Gabriel
Ribichini, Andrea
Abstract (EN)
In this paper we show how PRAM algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the W-Stream model. 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 yield near-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
W-stream model; combinatorial problems; streaming; PRAM algorithms

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
    Adapting parallel algorithms to the W-Stream model, with applications to graph problems 
    Ribichini, Andrea; Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil (2007) Communication / Conférence
  • Thumbnail
    Streaming Algorithms for Online Selection Problems 
    Correa, José; Dütting, Paul; Fischer, Felix; Schewior, Kevin; Ziliotto, Bruno (2021) Communication / Conférence
  • Thumbnail
    A parallel in time approach for quantum control: the parareal algorithm 
    Maday, Yvon; Turinici, Gabriel (2002) Communication / Conférence
  • Thumbnail
    Parallel in time algorithms for quantum control: the parareal time discretization scheme 
    Maday, Yvon; Turinici, Gabriel (2003) Article accepté pour publication ou publié
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