Michael Elkin
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 Scholar
Digital 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 ...
Reviews
Burkhard Englert
Computing the shortest paths between all vertices in a graph is a very important problem. It has many applications and can be used to solve problems like network routing, where the goal is to find the shortest path for data packets to take through a switching network. It is also used in more general search algorithms for a variety of problems, ranging from automated circuit layout to speech recognition. Algorithms that solve this problem generally involve nontrivial matrix multiplication, and as a result are impractical since their time complexities involve huge constants. Moreover, the currently best-known time complexity of algorithms of this type is O(n ^ 2.376), where n is the number of vertices in the graph. Often, approximations are cheaper to compute than exact values. In the s-sources almost shortest path (s-ASP) problem, given an unweighted, undirected graph G=(V, E) and a subset S of V of s sources, the goal is to compute paths between all the pairs of nodes (u, w) in S x V. The length of the computed path must be close to the actual distance d(u,w) between the nodes u and w in G, such that the length returned by the algorithm is at most α · d(u,w) + β. Here, α is called the multiplicative term of the error, while β is the additive term. This paper provides an important, new, and more efficient solution to this problem. It begins with a description of the problem, followed by a comparison of the new solution with previous results and a summary. The second and third sections contain the actual technical contributions of the paper. Both begin with overviews of the subsequent constructions. This significantly helps the reader in understanding the protocols. In the second section, a solution of the sequential s-ASP and the all pairs almost shortest path (APASP) problem is presented. The new algorithm has a running time of O(|E| · n ^ __?__ + s · n ^(1+ ζ)) with a multiplicative error of 1+ ε and an additive error of β(ζ,__?__,ε), where β(ζ,__?__,ε) is a constant whenever 0 < ζ,__?__,ε < 1 for arbitrarily small constants ζ,__?__ and ε. Then, in the third part, the first distributed protocol for constructing (1+ε, β) spanners is presented. This protocol has a near optimal communication complexity, and is used to provide a distributed protocol for computing almost shortest paths. Both the second and third parts conclude with an extension of the respective results to weighted graphs. This is by no means an introductory paper about the construction of almost shortest paths. The author uses a multitude of appropriate notations that require the reader's full attention. In the end, however, the reader's patience will be rewarded with a very insightful presentation. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments