An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
Madhumangal Pal, Sukumar Mondal, Debashis Bera, Tapan Kumar Pal · International Journal of Computer Mathematics · 2000
In this paper, a parallel algorithm is presented to find all cut-vertices and blocks of an interval graph. If the list of sorted end points of the intervals of an interval graph is given then the proposed algorithm takes O(log n) time and O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n).