DocumentCode :
2711742
Title :
Computing k-Vertex Connectivity on an Interval Graph
Author :
Kao, Tzong-Wann ; Horng, Shi-Jinn
Volume :
3
fYear :
1994
fDate :
15-19 Aug. 1994
Firstpage :
218
Lastpage :
221
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.
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing, 1994. ICPP 1994 Volume 3. International Conference on
Conference_Location :
North Carolina, USA
ISSN :
0190-3918
Print_ISBN :
0-8493-2493-9
Type :
conf
DOI :
10.1109/ICPP.1994.74
Filename :
5727862
Link To Document :
بازگشت