Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2004, Vol. 5 Issue (9): 1135-1143    DOI: 10.1631/jzus.2004.1135
Applied Mathematics     
Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
MISHRA P.K.
Department of Applied Mathematics, Birla Institute of Technology, Mesra-Ranchi, 835215, India
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.

Key words： Parallel algorithms      Shortest-paths problem      Interval graphs     
Received: 13 November 2003     
CLC:  O29  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
MISHRA P.K.
Cite this article:

MISHRA P.K.. Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2004, 5(9): 1135-1143.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2004.1135     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2004/V5/I9/1135

[1] MISHRA P.K.. An efficient parallel algorithm for shortest paths in planar layered digraphs[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2004, 5(5): 518-527.