An optimal parallel algorithm for all-pairs shortest paths on unweighted interval graphs
Madhumangal Pal, Gobinda Prashad Bhattacharjee · Nordic journal of computing · 1997
A cost optimal parallel algorithm is presented to find the all-pairs shortest paths on an unweighted interval graph which takes O(n/p + log n) time on an EREW PRAM, where np and n represent respectively the number of processors and the number of vertices of the graph.