Full Text:   <1298>

CLC number: O29

On-line Access: 

Received: 2003-07-21

Revision Accepted: 2003-11-04

Crosschecked: 0000-00-00

Cited: 0

Clicked: 2784

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.5 P.518~527


An efficient parallel algorithm for shortest paths in planar layered digraphs

Author(s):  MISHRA P.K.

Affiliation(s):  Dept. 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, Planar layered digraphs

Share this article to: More

MISHRA P.K.. An efficient parallel algorithm for shortest paths in planar layered digraphs[J]. Journal of Zhejiang University Science A, 2004, 5(5): 518~527.

@article{title="An efficient parallel algorithm for shortest paths in planar layered digraphs",
author="MISHRA P.K.",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T An efficient parallel algorithm for shortest paths in planar layered digraphs
%J Journal of Zhejiang University SCIENCE A
%V 5
%N 5
%P 518~527
%@ 1869-1951
%D 2004
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2004.0518

T1 - An efficient parallel algorithm for shortest paths in planar layered digraphs
J0 - Journal of Zhejiang University Science A
VL - 5
IS - 5
SP - 518
EP - 527
%@ 1869-1951
Y1 - 2004
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2004.0518

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log3n) time with nprocessors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

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


[1] Aggarwal, A., Park, J., 1988. Notes on Searching Dimensional Monotone Arrays. Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, p.496-512.

[2] Alon, N., Galil, Z., 1991. On the Exponent of the All Pairs Shortest Path Problem. Proc. 32th Annual IEEE Symposium on Foundations of Computer Sciences,32:569-575.

[3] Apostolico, A., Atallah, M.J., Larmore, L., Mc Faddin, H.S., 1990. Efficient parallel algorithms for editing and related problems.SIAM Journal on Computing,19:968-988.

[4] Atallah, M.J., 1990. A Faster Parallel Algorithm for A Matrix Searching Problem. Proc. 2th Scandinaviam Workshop on Algorithm Theory, p.193-200.

[5] Bellman, R., 1958. On a routing problem.Quarterly Journal of Applied Mathematics,16:87-90.

[6] Cohen, E., 1993. Efficient Parallel Shortest Paths in Digraphs with A Separator Decomposition. Proc. 5th Annual Symposium on Parallel Algorithms and Architectures, p.57-67.

[7] Coremen, T.H., 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.

[8] Delche, A.L., Kosarju, S.R., 1992. An N.C. Algorithm for Evaluating Monotone Planar Circuits.

[9] Di Battisa, G., Nardelli, E., 1987. An Algorithm for Testing Planarity of Hierarchical Graphs. Proc. Workshop WG 86, Bernierd, p.277-289.

[10] Dijkastra, E.W., 1995. A note on two problems in connection with graphs.Numer. Math.,1:269-271.

[11] Fredericckson, G., 1987. Fast algorithms for shortest paths in planar graphs with Applications.SIAM J. Comput.,16:1004-1022.

[12] Fredman, M.L., Tarjan, R.E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the ACM,34(3):596-615.

[13] Garit, H., Miller, G.L., 1987. A Parallel Algorithm for finding Separator in Planar Graphs. Proc. 28th Annual IEEE Symposium on Foundation of Computer Science, p.238-248.

[14] Generich, H.J., Lautenbach, K., 1973. Synchronisations graphics.Acta Inform,2:513-520.

[15] Gondram, M., Minoux, M., 1984. In Graphs and Algorithms. Willey Interscience, New York, p.143-161.

[16] J

[17] Klein, P.N., Subramanian, S., 1993. A Linear Processor Polylog-time Algorithm for Shortest Path in Planar Graphs. Proc. IEEE Symposium on Foundation of Computer Science, p.259-270.

[18] Levcopoulos, C., Lingas, A., 1992. There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees.Algorithmica,8(3):251-256.

[19] Lempel, A., Even, Cederbaum, S., 1986. An Algorithm for Planitry Testing of Graphs. Proc. Internet. Symposium, p.215-232.

[20] Lipton, R.J., Tarjan, R.E., 1979. A separator theorem for planar graphs.SIAM J. Appl. Math.,36:177-189.

[21] Lipton, R.J., Tarjan, R.E., 1980. Application of a planar separator theorem.SIAM J. Appl. Math.,9:615-627.

[22] Miller, G.L., Thurston, W., 1986. Separator in Two and Three Dimensions. Proc. 22nd Annual ACM Symposium on Theory of Computing, p.300-309.

[23] Mishra, P.K., Sharma, C.K., 1997. A Computational Study of An Efficient Shortest Path Algorithms in C-programming Language. Proc. of 5th International Conference on Application of HPC in Engineering, Santiago de Compstela, Spain.

[24] Mishra, P.K., Sharma, C.K., 1999. An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs. Proc. of 65th Annual Conference of Indian Mathematical society, India,2:635-654.

[25] Preparta, P.P., Shamons, M.I., 1985. Computational Geometry. Sringer Verlag, New-York.

[26] Tamassia, R., Preparta, P.P., 1990. Dynamic maintenance of planar digraphs with applications.Algorithmica,5:509-527.

Open peer comments: Debate/Discuss/Question/Opinion


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