Similar articles

Abstract: This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log³n) 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.

[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.