A parallel randomized approximation scheme for shortest paths

ABSTRACT

We give a randomized parallel algorithm for approximate shortest path computation in an undirected weighted graph. The algorithm is based on a technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search. It has application, e.g., in approximate solution of multicommodity flow problems with unit capacities. We also show how to adapt the algorithm to perform better for planar graphs.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: D. Eppstein and Z. Galil, "Parallel algorithmic techniques for Combinatorial Computation,"preprint, Columbia University (1988).
• 3: G. N. Frederickson, "Shortest path problems in planar graphs," Proceedings, 2#th Symposium on Foundalions of Computer Science (1983).
• 4: H. Gazit and G. L. Miller, "A Parallel Algorithm for finding a Separator in Planar Graphs," Proceedings, 28lh Symposium on Foundations of Compuler Science(1987) pp. 238-248
• 5: Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
• 6: H. Gazit and G. Miller, "A parallel algorithm for finding a separator in planar graphs," Proceedlings, 28th Symposium on Foundations of Computer Science (1987) pp. 238-248.
• 7: H. Gazit and G.L. Miller "A Deterministic Parallel Algorithm for Finding a Separator in Planar Graphs," manuscript.
• 8: Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
• 9: M.-Y. Kao , P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.181-192, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100237]
• 10: Philip N. Klein, A Parallel Randomized Approximation Scheme for Shortest Paths, Brown University, Providence, RI, 1991
• 11: P. Klein and S. Kang, "Approximating concurrent flow with uniform demands and capacities" an implementation," submitted to First DI- MACS International Algorithm Implementation Challenge.
• 12: P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
• 13: F. T. Leighton and S. Rao, "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms", Proceedings, 29th Symposium on Foundations of Compuler Science (1988), pp. 422-431.
• 14: R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Algebraic and Discrete Methods, 36(2):177-189, April 1979.
• 15: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 16: G. L. Miller, personal communication (1991).
• 17: G. L. Miller, S. Teng and S. A. Vavasis "A Unified Geometric Approah to Graph Separators," Proceedings, 32nd A CM Symposium on Theory of Computing, 1991
• 18: P Raghavan , C D Thompson, Provably good routing in graphs: regular arrays, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.79-87, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22154]
• 19: P. Raghavan, Lecture Notes on Randomized Algorithms, preprint (1989).
• 20: G.E. Shannon and F. Wan, "Subdividing Planar Graphs in Parallel," Technical Report, Department of Computer Science Indiana University, Bloomington (1991)
• 21: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 22: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• 23: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Performance, Theory