Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

DOI10.1137/080737174zbMath1227.05231OpenAlexW2037489203MaRDI QIDQ5390579

Telikepalli Kavitha, Surender Baswana

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080737174

zbMATH Keywords

all-pairs small stretch distances

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (10)

Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ New pairwise spanners ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Shortest-path queries in static networks ⋮ Preprocess, set, query! ⋮ Fast approximate shortest paths in the congested clique ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs