Efficient Parallel Algorithms for Planar st-Graphs

Get BibTex-formatted data

Download

PDF

Author

Mikhail Atallah, Danny Z. Chen, Ovidiu Daescu

Tech report number

CERIAS TR 2003-15

Entry type

article

Abstract

Planar st-graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving fundamental problems on planar st-graphs. The problems we consider include all-pairs shortest paths in weighted planar st-graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st-graphs), and depth-first search in planar st-graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st-graphs, and involve schemes for partitioning planar st-graphs into sub-graphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st-graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.

Download

PDF

Date

2003

Booktitle

Algorithmica

Key alpha

Atallah

Pages

194-215

Affiliation

Purdue University

Publication Date

2003-01-01

Keywords

Algorithms, EREW PRAM, Merging, Multi-selection, Partitioning, Sorting, Parallel computing

Language

English

Location

A hard-copy of this is in the CERIAS Library

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Atallah,
	title = "Efficient Parallel Algorithms for Planar st-Graphs",
	author = "Mikhail Atallah, Danny Z. Chen, Ovidiu Daescu",
	year = "2003",
	booktitle = "Algorithmica",
	pages = "194-215",
	abstract = "Planar st-graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving fundamental problems on planar st-graphs. The problems we consider include all-pairs shortest paths in weighted planar st-graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st-graphs), and depth-first search in planar st-graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st-graphs, and involve schemes for partitioning planar st-graphs into sub-graphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2].  The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st-graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.",
	affiliation = "Purdue University",
	keywords = "Algorithms, EREW PRAM, Merging, Multi-selection, Partitioning, Sorting, Parallel computing",
	language = "English",
}