Ordered h-Level Graphs on the BSP Model

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The implementation of data structures on distributed memory models such as the bulk-synchronous parallel model, rather than shared memory ones such as the parallel random access machine, offers a serious challenge. In this work we undertake the architecture independent study of the computation and communication requirements of searchingordered h-level graphs, which include many of the standard data structures. Our methods are within a 1 +o(1) multiplicative factor of the respective sequential methods. While our methods are fairly simple themselves, description of their performance in terms of the BSP parameters is somewhat complicated. The main reward for quantifying these complications is that it enables software to be written once and for all that can be migrated efficiently among a variety of parallel machines.

Original languageEnglish (US)
Pages (from-to)98-110
Number of pages13
JournalJournal of Parallel and Distributed Computing
Volume49
Issue number1
DOIs
StatePublished - Feb 25 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Ordered h-Level Graphs on the BSP Model'. Together they form a unique fingerprint.

Cite this