Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
Madhumangal Pal, Gobinda Prashad Bhattacharjee · International Journal of Computer Mathematics · 1995
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.