๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximating Shortest Paths on Weighted Polyhedral Surfaces

โœ Scribed by M. Lanthier; A. Maheshwari; J. -R. Sack


Publisher
Springer
Year
2001
Tongue
English
Weight
689 KB
Volume
30
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


Algorithms for Approximate Shortest Path
โœ Lyudmil Aleksandrov; Hristo N. Djidjev; Hua Guo; Anil Maheshwari; Doron Nussbaum ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Springer ๐ŸŒ English โš– 919 KB
A new approach to all-pairs shortest pat
โœ Seth Pettie ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 380 KB

We present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in O(mn + n 2 log log n) time, improving on the long-standing bound of O(mn + n 2 log n) derived from an implementation of Dijkstra's algorithm with Fibonacci