NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Optimal parallel algorithms for problems modeled by a family of intervalsA family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. Computational tools are developed, and it is shown how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.
Document ID
19920061331
Document Type
Reprint (Version printed in journal)
External Source(s)
Authors
Olariu, Stephan (NASA Langley Research Center Hampton, VA, United States)
Schwing, James L. (NASA Langley Research Center Hampton, VA, United States)
Zhang, Jingyuan (Old Dominion University Norfolk, VA, United States)
Date Acquired
August 15, 2013
Publication Date
May 1, 1992
Publication Information
Publication: IEEE Transactions on Parallel and Distributed Systems
Volume: 3
Issue: 3 Ma
ISSN: 1045-9219
Subject Category
COMPUTER PROGRAMMING AND SOFTWARE
Funding Number(s)
CONTRACT_GRANT: NCC1-99
CONTRACT_GRANT: NSF CCR-89-09996
Distribution Limits
Public
Copyright
Other