Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time

DOI10.1145/1198513.1198518zbMath1321.68214OpenAlexW2157760787MaRDI QIDQ2944530

Surender Baswana, Sandeep Sen

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1198513.1198518

zbMATH Keywords

distancesshortest pathsspannersdistance queriesapproximate distance oracles

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (25)

Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Vertex fault tolerant additive spanners ⋮ Distributed distance computation and routing with small messages ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ New pairwise spanners ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Shortest-path queries in static networks ⋮ Transitive-Closure Spanners: A Survey ⋮ Unnamed Item ⋮ Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Distributed Spanner Approximation ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

This page was built for publication: Approximate distance oracles for unweighted graphs in expected O ( n ² ) time