Title :
Computing k-Vertex Connectivity on an Interval Graph
Author :
Kao, Tzong-Wann ; Horng, Shi-Jinn
Abstract :
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.
Conference_Titel :
Parallel Processing, 1994. ICPP 1994 Volume 3. International Conference on
Conference_Location :
North Carolina, USA
Print_ISBN :
0-8493-2493-9
DOI :
10.1109/ICPP.1994.74