The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
All-Pairs Almost Shortest Paths
Dorit Dor, Shay Halperin, Uri Zwick,
Pages. 1740-1759
Abstract
Contents 1. Introduction 2. Preliminaries 3. Algorithm apasp$_k$ 4. Algorithm $\overline{apasp}_k$ 5. Boolean matrix multiplication 6. Distance emulators 7. Stretched paths and distance 8. Concluding remarks and open problems
Key words graph algorithms, shortest paths, approximation algorithms, spanners, emulators
Mathmatical Subject Classification 05C85, 68Q25, 68R10, 05C38