All-Pairs Small-Stretch Paths

DOI10.1006/jagm.2000.1117zbMath0974.68150OpenAlexW2083534148WikidataQ60299164 ScholiaQ60299164MaRDI QIDQ2729642

Uri Zwick, Edith Cohen

Publication date: 23 July 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2000.1117

zbMATH Keywords

weighted undirected graph

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ New length bounds for cycle bases ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Approximating Shortest Paths in Graphs ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Fast approximate shortest paths in the congested clique ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item

This page was built for publication: All-Pairs Small-Stretch Paths