Parallel priority queue and list contraction: The BSP approach

Alexandras V. Gerbessiotis, Constantinos J. Siniolakis, Alexandre Tiskin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

In this paper we present efficient and practical extensions of the randomized Parallel Priority Queue (PPQ) algorithms of Ranade et al., and efficient randomized and deterministic algorithms for the problem of list contraction on the Bulk-Synchronous Parallel (BSP) model. We also present an experimental study of their performance. We show that our algorithms are communication efficient and achieve small multiplicative constant factors for a wide range of parallel machines.

Original languageEnglish (US)
Title of host publicationEuro-Par 1997 Parallel Processing - Third International Conference, Proceedings
PublisherSpringer Verlag
Pages409-416
Number of pages8
ISBN (Print)9783540634409
DOIs
StatePublished - 1997
Externally publishedYes
Event3rd International Conference on Parallel Processing, Euro-Par 1997 - Passau, Germany
Duration: Aug 26 1997Aug 29 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1300 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Parallel Processing, Euro-Par 1997
CountryGermany
CityPassau
Period8/26/978/29/97

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel priority queue and list contraction: The BSP approach'. Together they form a unique fingerprint.

Cite this