DocumentCode
3486814
Title
On the shortest path problem for permutation graphs
Author
Ibarra, Oscar H. ; Zheng, Qi
Author_Institution
Dept. of Comput. Sci., California Univ., Santa Barbara, CA, USA
fYear
1993
fDate
13-16 Apr 1993
Firstpage
198
Lastpage
204
Abstract
The authors show that the single-source shortest path problem for permutation graphs can be solved in O (logn ) time using O (n /logn ) processors on an EREW PRAM. As an application, they show that a minimum connected dominating set of a permutation graph can be found in O (logn ) time using O (n /logn ) processors. The algorithms are optimal with respect to the time-processor product
Keywords
computational complexity; computational geometry; random-access storage; EREW PRAM; minimum connected dominating set; permutation graphs; shortest path problem; time-processor product; Application software; Biological system modeling; Computational modeling; Computer science; Laboratories; Parallel algorithms; Phase change random access memory; Scientific computing; Sequences; Shortest path problem;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location
Newport, CA
Print_ISBN
0-8186-3442-1
Type
conf
DOI
10.1109/IPPS.1993.262881
Filename
262881
Link To Document