The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
D. Aingworth, C. Chekuri, P. Indyk, R. Motwani,
Pages. 1167-1181
Abstract
Contents 1. Introduction
2. Preliminaries and a basic algorithm
2.1. Extension to directed graphs
3. Estimating the diameter
3.1. Distinguishing diameter 2 from 4
3.2. Approximating the diameter
3.3. Extension to weighted graphs
4. Estimating APSP
5. Estimating $k$-pairs shortest paths
5.1. Application: randomized approximation scheme for diameter
6. Experimental results
7. Conclusions and further work
Key words diameter, shortest paths, matrix multipication
Mathmatical Subject Classification 05C12, 05C50, 05C85, 68Q20