Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time

Richard Cole, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

Abstract

We define a novel scheduling problem; it is solved in parallel by repeated, rapid, approximate reschedulings. This leads to the first optimal logarithmic time PRAM algorithm for list ranking. Companion papers show how to apply these results to obtain improved PRAM upper bounds for a variety of problems on graphs, including the following: connectivity, biconnectivity, Euler tour and st-numbering, and a number of problems on trees.

Original languageEnglish (US)
Pages (from-to)128-142
Number of pages15
JournalSIAM Journal on Computing
Volume17
Issue number1
DOIs
StatePublished - 1988

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time'. Together they form a unique fingerprint.

Cite this