All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
type: Item
instance of: scholarly article
title: All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
zbMATH Open document ID: 1161.68036
author: Surender Baswana
author: Vishrut Goyal
author: Sandeep Sen
published in: Theoretical Computer Science
publication date: 2009-02-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 5509591
zbMATH Keywords: shortest path
zbMATH Keywords: distance
zbMATH Keywords: spanner
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.10.018
OpenAlex ID: W2060877994
cites work: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
cites work: On the exponent of all pairs shortest path problem
cites work: Near-Linear Time Construction of Sparse Neighborhood Covers
cites work: Q5501268
cites work: Faster Approximation of Distances in Graphs
cites work: More algorithms for all-pairs shortest paths in weighted graphs
cites work: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
cites work: Polylog-time and near-linear work approximation scheme for undirected shortest paths
cites work: All-pairs small-stretch paths
cites work: Matrix multiplication via arithmetic progressions
cites work: All-Pairs Almost Shortest Paths
cites work: Computing almost shortest paths
cites work: A new approach to all-pairs shortest paths on real-weighted graphs
cites work: Automata, Languages and Programming
cites work: Gaussian elimination is not optimal
cites work: Subcubic cost algorithms for the all pairs shortest path problem
cites work: Approximate distance oracles
cites work: Q4796165
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
DOI: 10.1016/J.TCS.2008.10.018
description: scientific article; zbMATH DE number 5509591