Full Text:   <1262>

CLC number: O29

On-line Access: 

Received: 2003-11-13

Revision Accepted: 2004-01-08

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3621

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2004 Vol.5 No.9 P.1135~1143


Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs

Author(s):  MISHRA P.K.

Affiliation(s):  Department of Applied Mathematics, Birla Institute of Technology, Mesra-Ranchi, 835215, India

Corresponding email(s):   pkmishra@ieee.org, pkmishra@bitmesra.ac.in

Key Words:  Parallel algorithms, Shortest-paths problem, Interval graphs

Share this article to: More

MISHRA P.K.. Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs[J]. Journal of Zhejiang University Science A, 2004, 5(9): 1135~1143.

@article{title="Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs",
author="MISHRA P.K.",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
%J Journal of Zhejiang University SCIENCE A
%V 5
%N 9
%P 1135~1143
%@ 1869-1951
%D 2004
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2004.1135

T1 - Optimal parallel Algorithm for Shortest Paths Problem on Interval Graphs
J0 - Journal of Zhejiang University Science A
VL - 5
IS - 9
SP - 1135
EP - 1143
%@ 1869-1951
Y1 - 2004
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2004.1135

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Aho, A.V., Hopcroft, J.E., Ullman, J.D., 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA.

[2] Atallah, M.J., Chen, D.Z., 1989. An optimal parallel algorithm for the minimum circle cover problem. Information Processing Letters, 32:159-165.

[3] Bertossi, A.A., 1988. Parallel circle cover algorithms. Information Processing Letters, 27:133-139.

[4] Booth, K.S., Luekher, G.S., 1976. Testing for the consecutive ones properly, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13:335-379.

[5] Chen, D.Z., Lee, D.T., 1994. Solving the All Pair Shortest-path Problem on Interval and Circular-arc Graphs. Proceedings of the 8th International Parallel Processing Symposium, Cancun, Mexico, p.224-228.

[6] Gabow, H.N., Tarjan, R.E., 1985. A linear time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30:209-221.

[7] Golumbic, M.C., 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

[8] Gupta, U.I., Lee, D.T., Leung, J.Y.T., 1982. Efficient algorithms for interval graphs and circular-arc graphs. Networks, 12:459-467.

[9] Ibarrra, O.H., Wang, H., Zheng, Q., 1992. Minimum Cover and Single Source Shortest-path Problems for Weighted Interval Graphs and Circular-Arc Graphs. Proceeding of the 30th Annual Allerton Conference on Communication, Control and Computing, University of Illinois, Urbana, p.575-584.

[10] Lee, C.C., Lee, D.T., 1984. On a circle cover minimization problem. Information Processing Letters, 18:109-115.

[11] Mishra, P.K., Sharma, C.K., 1997. A Computational Study of the Shortest-path Algorithms in C-Programming Language. Proc. Fifth International Conference on Applications of High Performance Computing in Engineering, Santiago de Compostela, Spain.

[12] Mishra, P.K., Sharma, C.K., 2002. An efficient implementation of scaling algorithms for the shortest-paths problem. News Bulletin of Calcutta Mathematical Society, 27:342-351.

[13] Mishra, P.K., 2004. An efficient parallel algorithm for shortest-paths in planar layered digraphs. Journal of Zhejiang University SCIENCE, 5(5):518-527.

Open peer comments: Debate/Discuss/Question/Opinion


Sovan Samanta@research scholar<navosmath@gmail.com>

2011-01-25 10:28:45

Respected sir

please give the paper as it is urgent for me.I will be thank ful to you.--

sovan samantaV.U.

Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE