Abstract
We study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-ASP</i>) problem. Given an unweighted graph <i>G</i> = (<i>V,E</i>), and a subset <i>S</i> ⊆ <i>V</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between all the pairs of nodes <i>S</i> × <i>V</i>. We devise an algorithm with running time <i>O</i>(∣<i>E</i>∣<i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ)</sup> for this problem that computes the paths <i>P</i><sub><i>u,w</i></sub> for all pairs (<i>u,w</i>) ∈ <i>S</i> × <i>V</i> such that the length of <i>P</i><sub><i>u,w</i></sub> is at most (1 + ε) <i>d</i><sub><i>G</i></sub>(<i>u,w</i>) + β(ζ,ρ,ε), and β(ζ,ρ,ε) is constant when ζ, ρ, and ε are arbitrarily small constants.
We also devise a distributed protocol for the <i>s</i>-ASP problem that computes the paths <i>P</i><inf><i>u,w</i></inf> as above, and has time and communication complexities of <i>O</i>(<i>s</i> · <i>Diam(G)</i> + <i>n</i><sup>1 + ζ/2</sup>) (respectively, <i>O</i>(<i>s</i> · <i>Diam(G)</i> log<sup>3</sup> <i>n</i> + <i>n</i><sup>1 + ζ/2</sup> log <i>n</i>)) and <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ)</sup> (respectively, <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ</sup> + <i>n</i><sup>1 + ρ + ζ(ρ − ζ/2)/2)) in the synchronous (respectively asynchronous) setting.
Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 + ε, β(ζ,ρ, ε))-spanners of size <i>O</i>(<i>n</i><sup>1 + ζ</sup>), developed in this article. This algorithm has running time of <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup>), which is significantly faster than the previously known algorithm given in Elkin and Peleg [2001], whose running time is <i>Õ</i>(<i>n</i><sup>2 + ρ</sup>). We also develop the first distributed protocol for constructing (1 + ε,β)-spanners. The communication complexity of this protocol is near optimal.
- Awerbuch, B., Berger, B., Cowen, L., and Peleg, D. 1998. Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28, 1, 263--277. Google ScholarDigital Library
- Awerbuch, B., Baratz, A., and Peleg, D. 1991. Efficient broadcast and light-weight spanners. Unpublished manuscript.Google Scholar
- Aingworth, D., Chekuri, C., Indyk, P., and Motwani, R. 1996. Fast estimation of diameter and shortest paths (without matrix multiplication). In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA). 547--553. Google ScholarDigital Library
- Althöfer, I., Das, G., Dobkin, D., and Joseph, D. 1990. Generating sparse spanners for weighted graphs. In Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 447. Springer-Verlag, New York, NY/Berlin, Germany, 26--37. Google ScholarDigital Library
- Awerbuch, B., and Gallagher, G. 1987. A new distributed algorithm to find breadth first search trees. IEEE Trans. Inform. Theory. IT-33, 3, 315--322. Google ScholarDigital Library
- Alon, N., Galil, Z., and Margalit, O. 1997. On the exponent of the all pairs shortest paths problem. J. Comput Syst. Sci. 54, 255--262. Google ScholarDigital Library
- Alon, N., Galil, Z., Margalit, O., and Naor, M. 1992. Witnesses for Boolean matrix multiplication and for shortest paths. In Proceeedings of the 33rd IEEE Symposium on Foundations of Computer Science (Pittsburgh, PA). 417--426.Google Scholar
- Awerbuch, B., and Peleg, D. 1990. Network synchronization with polylogarithmic overhead. In Proceedings of the 31st Symposium on Foundations of Computer Science. 514--522.Google Scholar
- Afek, Y., and Ricklin, M. 1992. A paradigm for running distributed algorithms. In Proceedings of the 6th Workshop on Distributed Algorithms. Lecture Notes in Computer Science, vol. 647. Springer, New York, NY/Berlin, Germany, 1--10. Google ScholarDigital Library
- Awerbuch, B. 1985a. Complexity of network synchronization. J. ACM 4, 804--823. Google ScholarDigital Library
- Awerbuch, B. 1985b. Reducing complexities of the distributed max-flow and the breadth-first-search algorithms by means of network synchronization. Networks 15, 425--437.Google ScholarCross Ref
- Awerbuch, B. 1989. Distributed shortest paths algorithms. In Proceedings of the 21st ACM Symposium on Theory of Computing. 230--240. Google ScholarDigital Library
- Bollobas, B., Coppersmith, D., and Elkin, M. L. 2003. Sparse distance preservers and additive spanners. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'03, Baltimore, MD, January.) Google ScholarDigital Library
- Baswana, S., and Sen, S. 2003. A simple linear time algorithm for computing a (2k − 1)-spanner of O(n1+1/k) size in weighted graphs. In Proceedings of the International Colloquium on Automata, Languages and Computing. 284--296. Google ScholarDigital Library
- Chandra, B., Das, G., Narasimhan, G., and Soares, J. 1992. New sparseness results on graph spanners. In Proceedings of the 8th ACM Symposium on Computational Geometry. 192--201. Google ScholarDigital Library
- Chew, L. P. 1986. There is a planar graph almost as good as complete graph. In Proceedings of the 2nd Symposium on Computational Geometry. 169--177. Google ScholarDigital Library
- Cohen, E. 1993. Fast algorithms for constructing t-spanners and paths of stretch t. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science. IEEE Press, Piscataway, NJ, 648--658.Google ScholarDigital Library
- Cohen, E. 1994. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In Proceedings of the 26th ACM Symposium on Theory of Computation. 16--26. Google ScholarDigital Library
- Dor, D., Halperin, S., and Zwick, U. 2000. All pairs almost shortest paths. SIAM J. Comput. 29, 1740--1759. Google ScholarDigital Library
- Dobkin, D. P., Friedman, S. J., and Supowit, K. J. 1987. Delaunay graphs are almost as good as complete graphs. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. 20--26.Google Scholar
- Elkin, M. 2001. Computing almost shortest paths, In Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (Newport, RI, August). 53--63. Google ScholarDigital Library
- Elkin, M., and Peleg, D. 2001. (1 + ε,β)-spanner constructions for general graphs. In Proceedings of the 33rd ACM Symposium on Theory of Computing (Crete, Greece, July). Full version is to appear in SIAM Journal of Computing. Google ScholarDigital Library
- Elkin, M., and Zhang, J. 2004. Efficient algorithms for constructing (1 + ε,β)-spanners in the distributed and streaming models. In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (St. John's, Newfoundland, Canada, July). Google ScholarDigital Library
- Frederickson, G. N. 1985. Trade-offs for selection in distributed networks. In Proceedings of the 2nd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 182. Springer, Berlin, Germany, 143--150. Google ScholarDigital Library
- Gallagher, R. G. 1982. Distributed minimum hop algorithms. Tech. rep. LIDS-P-175. Laboratory for Information and Decision Systems, MIT, Cambridge, MA.Google Scholar
- Galil, Z., and Margalit, O. 1993. Witnesses for Boolean matrix multiplication. J. Complex. 9, 201--221. Google ScholarDigital Library
- Galil, Z., and Margalit, O. 1997. All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci. 54, 243--254. Google ScholarDigital Library
- Kortsarz, G. 2001. On the hardness of approximating spanners. Algorithmica 30, 3, 432--450.Google ScholarCross Ref
- Peleg, D. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, Press, Philadelphia, PA. Google ScholarCross Ref
- Peleg, D., and Schäffer, A. 1989. Graph spanners, J. Graph Theor. 13, 99--116.Google ScholarCross Ref
- Peleg, D., and Ullman, J. D. 1989. An optimal synchronizer for the hypercube. SIAM J. Comput. 18 740--747. Google ScholarDigital Library
- Roditty, L., and Zwick, U. 2004. Dynamic approximate all-pairs shortest paths in undirected graphs. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (Rome, Italy, October). Google ScholarDigital Library
- Roditty, L., Thorup, M., and Zwick, U. 2002. Roundtrip spanners and roundtrip routing in directed graphs. Proceedings of the Symposium on Discrete Algorithms. 844--851. Google ScholarDigital Library
- Seidel, R. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400--403. Google ScholarDigital Library
- Segall, A. 1983. Distributed network protocols. IEEE Trans. Inform. Theor. IT-29, 1 (Jan.), 23--34.Google ScholarCross Ref
- Thorup, M. 2001. Compact oracles for reachability and approximate distances in planar digraphs. Proceedings of the Symposium on Foundations of Computer Science. 242--251. Google ScholarDigital Library
- Thorup, M., and Zwick, U. 2001a. Compact routing schemes. In Proceedings of the Symposium on Parallel Algorithms and Architecture. 1--10. Google ScholarDigital Library
- Thorup, M., and Zwick, U. 2001b. Approximate distance oracles. In Proceedings of the Symposium on Theory of Computing. 183--192. Google ScholarDigital Library
Index Terms
- Computing almost shortest paths
Recommendations
Computing almost shortest paths
PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computingWe study the s-sources almost shortest paths (shortly, s-ASP) problem. Given an unweighted graph G = (V, E), and a subset S ⊈ V of s nodes, the goal is to compute almost shortest paths between all the pairs of nodes S x V. We devise an algorithm with ...
Distributed approximation algorithms for weighted shortest paths
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingA distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the ...
Comments