Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph

Authors:

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.

This publication has 10 references indexed in Scilit: