article

Streaming algorithm for graph spanners---single pass and constant processing time per edge

Author:

Surender BaswanaAuthors Info & Claims

Information Processing Letters, Volume 106, Issue 3

Pages 110 - 114

https://doi.org/10.1016/j.ipl.2007.11.001

Published: 01 April 2008 Publication History

Abstract

No abstract available.

References

[1]

Althöfer, I., Das, G., Dobkin, D.P., Joseph, D. and Soares, J., On sparse spanners of weighted graphs. Discrete and Computational Geometry. v9. 81-100.

Google Scholar

[2]

Ausiello, G., Demetrescu, C., Franciosa, P.G., Italiano, G.F. and Ribichini, A., Small stretch spanners in the streaming model: New algorithms and experiments. In: LNCS, vol. 4698. Springer. pp. 605-617.

Digital Library

Google Scholar

[3]

Awerbuch, B., Complexity of network synchronization. Journal of ACM. 804-823.

Digital Library

Google Scholar

[4]

Baswana, S. and Sen, S., A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures and Algorithms. v30. 532-563.

Digital Library

Google Scholar

[5]

Elkin, M., Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: Lecture Notes in Comput. Sci., vol. 4596. Springer. pp. 716-727.

Digital Library

Google Scholar

[6]

Elkin, M. and Peleg, D., Strong inapproximability of the basic k-spanner problem. In: LNCS, vol. 1853. Springer. pp. 636-648.

Digital Library

Google Scholar

[7]

Erdős, P., Extremal problems in graph theory. In: Proc. Sympos. Smolenice, vol. 1963. Publ. House Czechoslovak Acad. Sci., Prague. pp. 29-36.

Google Scholar

[8]

Feigenbaum, J., Kannan, S., McGregor, A., Suri, S. and Zhang, J., On graph problems in a semi-streaming model. In: LNCS, vol. 3142. Springer. pp. 531-543.

Google Scholar

[9]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang, Graph distances in the streaming model: the value of space, in: Proceedings of 16th Annual ACM--SIAM Symposium on Discrete Algorithms, 2005, pp. 745--754

Digital Library

Google Scholar

[10]

S. Halperin, U. Zwick, Linear time deterministic algorithm for computing spanners for unweighted graphs, unpublished manuscript, 1996

Google Scholar

[11]

Henzinger, M.R., Raghavan, P. and Rajagopalan, S., Computing on data streams. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 50. pp. 107-118.

Digital Library

Google Scholar

[12]

McGregor, A., Finding graph matchings in streaming model. In: LNCS, vol. 3624. Springer. pp. 170-181.

Digital Library

Google Scholar

[13]

Peleg, D. and Schäffer, A., Graph spanners. Journal of Graph Theory. v13. 99-116.

Google Scholar

Cited By

View all

Filtser ALe HLeonardi SGupta A(2022)Locality-sensitive orderings and applications to reliable spannersProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520042(1066-1079)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520042
Elkin MTrehan CMilani AWoelfel P(2022)Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538469(57-59)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538469
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Show More Cited By

Index Terms

Streaming algorithm for graph spanners---single pass and constant processing time per edge
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

Let G = ( V , E ) be an undirected weighted graph on | V | = n vertices and | E | = m edges. A t -spanner of the graph G , for any t ý 1, is a subgraph ( V , E _S), E _S ý E , such that the distance between any pair of vertices in ...
All-pairs nearly 2-approximate shortest paths in O(n2polylogn) time

Let G=(V,E) be an unweighted undirected graph on |V|=n vertices and |E|=m edges. Let @d(u,v) denote the distance between vertices u,v@?V. An algorithm is said to compute all-pairs t-approximate shortest-paths/distances, for some t>=1, if for each pair ...
Multipath spanners
SIROCCO'10: Proceedings of the 17th international conference on Structural Information and Communication Complexity

This paper concerns graph spanners that approximate multipaths between pair of vertices of an undirected graphs with n vertices. Classically, a spanner H of stretch s for a graph G is a spanning subgraph such that the distance in H between any two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 106, Issue 3

April, 2008

46 pages

ISSN:0020-0190

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Filtser ALe HLeonardi SGupta A(2022)Locality-sensitive orderings and applications to reliable spannersProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520042(1066-1079)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520042
Elkin MTrehan CMilani AWoelfel P(2022)Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538469(57-59)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538469
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Dory MFischer OKhoury SLeitersdorf DMiller ACensor-Hillel K(2021)Constant-Round Spanners and Shortest Paths in Congested Clique and MPCProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467928(223-233)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467928
Elkin MNeiman O(2018)Efficient Algorithms for Constructing Very Sparse Spanners and EmulatorsACM Transactions on Algorithms10.1145/327465115:1(1-29)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3274651
Censor-Hillel KKavitha TPaz AYehudayoff A(2018)Distributed construction of purely additive spannersDistributed Computing10.1007/s00446-017-0306-231:3(223-240)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00446-017-0306-2
Elkin MNeiman OKlein P(2017)Efficient algorithms for constructing very sparse spanners and emulatorsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039728(652-669)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039728
Dolgorsuren BXu WKhan KJeong BLee YKim JKim YGeller JChoi WLeung CPark Y(2016)SP2Proceedings of the Sixth International Conference on Emerging Databases: Technologies, Applications, and Theory10.1145/3007818.3007837(43-50)Online publication date: 17-Oct-2016
https://dl.acm.org/doi/10.1145/3007818.3007837
Emek YRosén A(2016)Semi-Streaming Set CoverACM Transactions on Algorithms10.1145/295732213:1(1-22)Online publication date: 15-Nov-2016
https://dl.acm.org/doi/10.1145/2957322
Henzinger MKrinninger SNanongkai DWichs DMansour Y(2016)A deterministic almost-tight distributed algorithm for approximating single-source shortest pathsProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897638(489-498)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2897518.2897638
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

All-pairs nearly 2-approximate shortest paths in O(n2polylogn) time

Multipath spanners

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations