Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
From MaRDI portal
Publication:2944530
DOI10.1145/1198513.1198518zbMath1321.68214OpenAlexW2157760787MaRDI QIDQ2944530
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
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (24)
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 ⋮ 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 2 ) time
