Computing k-Vertex Connectivity on an Interval Graph
Tzong‐Wann Kao, Shi-Jinn Horng · 1994
We show that determine the maximum number of vertex connectivity, test k-vertex connectivity and determine the maximum number of vertex disjoint I_s - l_t paths of interval graphs can be solved either in O(log n) time using O{n) processors for the Unsorted case or in O{logn) time using O{n/logn) processors for the sorted case, and find k-vertex disjoint I_s - I_t paths of interval graphs can be solved in O{k logn) time using O{n^{2}/logn) processors on the EREW PRAM model, respectively. All parallel algorithms are optimal with respect to the time-processor product except the last one.