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
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;
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
DOI :
10.1109/IPPS.1993.262881
