Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
Authors:
- 1 January 1995
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 59 (1-2) , 1-13
Abstract
An 0(n) time sequential algorithm is presented for computing the diameter and the center of an interval graph with n vertices given the interval representation of the graph as a sorted list of endpoints. Two parallel algorithms are also presented for the same problems. These algorithms work in 0(n/P + log n) time on the EREW PRAM using P processors and 0(n) space.Keywords
This publication has 10 references indexed in Scilit:
- Optimal parallel algorithms for problems modeled by a family of intervalsIEEE Transactions on Parallel and Distributed Systems, 1992
- Breadth-first traversal of trees and integer sorting in parallelInformation Processing Letters, 1992
- An optimal algorithm to solve the all‐pair shortest path problem on interval graphsNetworks, 1992
- A unified approach to parallel depth-first traversals of general treesInformation Processing Letters, 1991
- A simple linear-time algorithm for computing the center of an interval graphInternational Journal of Computer Mathematics, 1990
- Parallel Merge SortSIAM Journal on Computing, 1988
- A unified approach to domination problems on interval graphsInformation Processing Letters, 1988
- Computation of the center and diameter of outerplanar graphsDiscrete Applied Mathematics, 1980
- Graph Theory and Its Applications to Problems of Society1978
- Minimax Location of a Facility in a NetworkTransportation Science, 1972