Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing. 28(4), 1167–1181 (1999)

Alon, N., Galil, Z., Margalit, O.: On the exponet of the all pairs shortest path problem. In: Proc. 32st IEEE Symposium on Foundations of Computer Science, pp. 569–575 (1991)

Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. Journal of Computer and System Sciences. 58(1), 137–147 (1999)

Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing, 28(1), 263–277 (1998)

Awerbuch, B., Patt-Shamir, B., Peleg, D., Saks, M.: Adapting to asynchronous dynamic networks. In: Proc. 24th ACM Symposium on Theory of Computing, pp. 557–570 (1992)

Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: Proc. 31st IEEE Symposium on Foundations of Computer Science, pp. 514–522 (1990)

Awerbuch, B., Peleg, D.: Routing with polynomial communication-space tradeoff. SIAM Journal on Discrete Mathematics. 5, 151–162 (1992)

Buchsbaum, A.L., Giancarlo, R., Westbrook, J.R.: On finding common neighborhoods in massive graphs. Theoretical Computer Science. 299(1-3), 707–718 (2003)

Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k-1)-spanner of O(n 1+1/k ) size in weighted graphs. In: Proc. International Colloq. on Automata, Languages and Computing, pp. 284–296 (2003)

Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in o(n 2log n) time. In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (2004)

Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. In: Proc 8th ACM Symposium on Computational Geometry, pp. 192–201 (1992)

Charikar, M., O’Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 30–39 (2003)

Cohen, E.: Fast algorithms for t-spanners and stretch-t paths. In: Proc. 34th IEEE Symposium on Foundation of Computer Science, pp. 648–658 (1993)

Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest-paths. In: Proc. 26th ACM Symposium on Theory of Computing, pp. 16–26 (1994)

Cohen, E., Zwick, U.: All pairs small stretch paths. Journal of Algorithms. 38, 335–353 (2001)

Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (2004)

Cole, R., Vishkin, U.: Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM Journal on Computing. 17, 128–142 (1988)

Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. SIAM Journal on Computing. 29, 1740–1759 (2000)

Elkin, M.: Computing almost shortest paths. In: Proc. 20th ACM Symposium on Principles of Distributed Computing, pp. 53–62 (2001)

Elkin, M.: A fast distributed protocol for constructing the minimum spanning tree. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 352–361 (2004)

Elkin, M., Peleg, D.: (1 + ∊,β)-spanner constructions for general graphs. In: Proc. 33rd Annual ACM Symp. on Theory of Computing, pp. 173–182 (2001)

Elkin, M., Zhang, J.: Efficient algorithms for constructing (1+ ∊, beta)-spanners in the distributed and streaming models. In: Proc. of 23rd Annual SIGACT-SIGOPS Symp. on Principles of Distributed Computing, PODC, pp. 160-168, St. John’s, Newfoundland, Canada (2004)

Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: Proc. 31st International Colloquium on Automata, Languages and Programming, LNCS vol. 3142, pp. 531–543 (2004)

Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph Distances in the Streaming Model: The Value of Space. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms pp. 745–754 (2005)

Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L 1 difference algorithm for massive data streams. SIAM Journal on Computing. 32(1), 131–151 (2002)

Galil, Z. Margalit, O.: All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences. 54(2), 243–254 (1997)

GMMO00 Guha, S., Mishra, N., Motwani, R., O’Callaghan, L.: Clustering data streams. In: Proc. 41th IEEE Symposium on Foundations of Computer Science, pp. 359–366 (2000)

Henzinger, M. R., Raghavan, P., Rajagopalan, S.: Computing on data streams. Technical Report 1998-001, DEC Systems Research Center (1998)

Indyk, P.: Stable distributions, pseudorandom generators, embeddings and data stream computation. In: Proc. 41th IEEE Symposium on Foundations of Computer Science, pp. 189–197 (2000)

Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Math. 5, 545–557 (1990)

Muthukrishnan, S.: Data streams: Algorithms and applications. 2003. Available at http://athos.rutgers.edu/∼muthu/stream-1-1.ps.

Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM, Philadelphia, PA (2000)

Peleg, D., Schäffer, A.: Graph spanners. Journal of Graph Theory. 13, 99–116 (1989)

Peleg, D., Ullman, J.: An optimal synchronizer for the hypercube. SIAM Journal on Computing. 18, 740–747 (1989)

Peleg, D., Upfal, E.: A tradeoff between space and efficiency for routing tables. Journal of ACM. 36(3), 510–530 (1989)

Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 844–851 (2002)

Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graph. Journal of Computer and System Sciences, 51(3), 400–403 (1995)

Zwick, U.: Exact and approximate distances in graphs - a survey. In: Proc. 9th European Symposium on Algorithms, pp. 33–48 (2001)