Article

Free access

Fast estimation of diameter and shortest paths (without matrix multiplication)

Authors:

D. Aingworth,

C. Chekuri,

R. MotwaniAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 547 - 553

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. In Proceedings of the 32nd Annual IEEE Symposium on Founds. tions of Computer Science, pages 569-575, 1991.

Digital Library

Google Scholar

[2]

N. Alon, Z. Galil, O. Margalit, and M Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths. In Proceedings of the 33nd Annual IEEE Symposium on Foundations of Computer Sci. ence, pages 417-426, 1992.

Google Scholar

[3]

J. Basch, S. Khanna, and R. Motwani. On Diameter Verification and Boolean Matrix Multiplication. Report No. STAN-CS-95-1544, Department of Computer Science, Stanford University (1995).

Digital Library

Google Scholar

[4]

B. Bollob~s. Random Graphs. Academic Press, 1985.

Google Scholar

[5]

Fan R.K. Chung. Diameters of Graphs: Old Problems and New Results. Congressus Numerantium, 60:295-317, 1987.

Google Scholar

[6]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.

Digital Library

Google Scholar

[7]

T. Feder and R. Motwani. Clique partitions, graph compression and speeding-up algorithms. In Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 123-133, 1991.

Digital Library

Google Scholar

[8]

D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974.

Google Scholar

[9]

D.E. Knuth The Stanford GraphBase: A platform for combinatorial computing. Addison-Wesley publishing company, 1993.

Crossref

Google Scholar

[10]

L. Lov~sz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975

Google Scholar

[11]

R.G. Seidel. On the all-pairs-shortest-path problem. In Proceedings of the 24th Annual A CM Symposium on Theory of Computing, pages 745-749, 1992.

Digital Library

Google Scholar

[12]

V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354-356, 1969.

Google Scholar

Cited By

View all

Bergamaschi THenzinger MGutenberg MWilliams VWein NMarx D(2021)New techniques and fine-grained hardness for dynamic near-additive spannersProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458174(1836-1855)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458174
Bodwin GKlein P(2017)Linear size distance preserversProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039725(600-615)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039725
Abboud ABodwin G(2017)The 4/3 Additive Spanner Exponent Is TightJournal of the ACM10.1145/308851164:4(1-20)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3088511
Show More Cited By

Index Terms

Fast estimation of diameter and shortest paths (without matrix multiplication)
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Randomness, geometry and discrete structures

Recommendations

Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n³). Unfortunately, all the new algorithms are based ...
Replacement Paths via Fast Matrix Multiplication
FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science

Let G be a directed edge-weighted graph and let P be a shortest path from s to t in G. The replacement paths problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
521
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bergamaschi THenzinger MGutenberg MWilliams VWein NMarx D(2021)New techniques and fine-grained hardness for dynamic near-additive spannersProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458174(1836-1855)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458174
Bodwin GKlein P(2017)Linear size distance preserversProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039725(600-615)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039725
Abboud ABodwin G(2017)The 4/3 Additive Spanner Exponent Is TightJournal of the ACM10.1145/308851164:4(1-20)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3088511
Abboud ABodwin GWichs DMansour Y(2016)The 4/3 additive spanner exponent is tightProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897555(351-361)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2897518.2897555
Takes FKosters W(2011)Determining the diameter of small world networksProceedings of the 20th ACM international conference on Information and knowledge management10.1145/2063576.2063748(1191-1196)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2063576.2063748
Magnien CLatapy MHabib M(2009)Fast computation of empirically tight bounds for the diameter of massive graphsACM Journal of Experimental Algorithmics10.1145/1412228.145526613(1.10-1.9)Online publication date: 23-Feb-2009
https://dl.acm.org/doi/10.1145/1412228.1455266
Goldstein DKobayashi K(2006)On the complexity of the “most general” firing squad synchronization problemProceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science10.1007/11672142_57(696-711)Online publication date: 23-Feb-2006
https://dl.acm.org/doi/10.1007/11672142_57
Elkin M(2005)Computing almost shortest pathsACM Transactions on Algorithms10.1145/1103963.11039681:2(283-323)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1145/1103963.1103968
Cowen LWagner C(2004)Compact roundtrip routing in directed networksJournal of Algorithms10.1016/j.jalgor.2003.08.00150:1(79-95)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1016/j.jalgor.2003.08.001
Gao JZhang LLarmore LGoemans M(2003)Well-separated pair decomposition for the unit-disk graph metric and its applicationsProceedings of the thirty-fifth annual ACM symposium on Theory of computing10.1145/780542.780613(483-492)Online publication date: 9-Jun-2003
https://dl.acm.org/doi/10.1145/780542.780613
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

Replacement Paths via Fast Matrix Multiplication