• 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 - Request a copy

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

Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil; Ribichini, Andrea (2011), Adapting parallel algorithms to the W-Stream model, with applications to graph problems, Theoretical Computer Science, 411, 44-46, p. 3994-4004. http://dx.doi.org/10.1016/j.tcs.2010.08.030

Type
Article accepté pour publication ou publié
Date
2011
Journal name
Theoretical Computer Science
Volume
411
Number
44-46
Publisher
Elsevier
Pages
3994-4004
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2010.08.030
Metadata
Show full item record
Author(s)
Moruz, Gabriel
Escoffier, Bruno
Demetrescu, Camil
Ribichini, Andrea
Abstract (EN)
In 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.
Subjects / Keywords
Data streaming model; Reductions to parallel algorithms; Graph problems

Related items

Showing items related by title and author.

  • 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
    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