Parallel Algorithms for Longest Increasing Chains in the Plane and Related Problems

Get BibTex-formatted data

Download

PDF

Author

Mikhail J. Atallah,Danny Z. Chen,Kevin S. Klenk

Tech report number

COAST TR 97-22

Entry type

article

Abstract

Given a set S of n points in the plane such that each point in S is associated with a non negative weight, we consider the problem of computing the single source longest increasing chains among the points in S. This problem is a generalization of the planar maximal layers problem. In this paper, we present a parallel algorithm that computes the single source longest increasing chains in the plane in O(log^2*n) time using O(n^2/log^3 n) processors in hte CREW PRAM computational model. We also have solved a related problem of computing the all-pairs longest paths in an n-node weighted planar st-graph, in O(log^2 n) time using O(n^2 / log n) CREW PRAM processors. Both of our parallel algorithms are an improvement over the previously best known results.

Download

PDF

Date

1997 – November

Journal

Parallel Processing Letters

Key alpha

Atallah

Volume

Publication Date

1900-01-01

Location

A hard-copy of this is in the Papers Cabinet

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 = "Parallel Algorithms for Longest Increasing Chains in the Plane and Related Problems",
	author = "Mikhail J. Atallah,Danny Z. Chen,Kevin S. Klenk",
	year = "1997",
	month = "November",
	journal = "Parallel Processing Letters",
	volume = "9",
	abstract = "Given a set S of n points in the plane such that each point in S is
associated with a non negative weight, we consider the problem of computing the single source longest increasing chains among the points in S. This problem
is a generalization of the planar maximal layers problem. In this
paper, we present a parallel algorithm that computes the single
source longest increasing chains in the plane in O(log^2*n) time
using O(n^2/log^3 n) processors in hte CREW PRAM computational
model. We also have solved a related problem of computing the
all-pairs longest paths in an n-node weighted planar st-graph, in
O(log^2 n) time using O(n^2 / log n) CREW PRAM processors. Both
of our parallel algorithms are an improvement over the previously
best known results.",
}