Approximate distance oracles for unweighted graphs in expected O(n^2) time
From MaRDI portal
Publication:2944530
DOI10.1145/1198513.1198518zbMATH Open1321.68214OpenAlexW2157760787MaRDI QIDQ2944530FDOQ2944530
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Cited In (31)
- Fault tolerant approximate BFS structures with additive stretch
- Graph spanners: a tutorial review
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Title not available (Why is that?)
- New approximation algorithms for minimum cycle bases of graphs
- \(f\)-sensitivity distance oracles and routing schemes
- Tree 3-spanners on generalized prisms of graphs
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Title not available (Why is that?)
- Distributed spanner approximation
- Transitive-closure spanners: a survey
- Distributed distance computation and routing with small messages
- Additive spanners and distance oracles in quadratic time
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Minimum \(t\)-spanners on subcubic graphs
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Polynomial algorithms for sparse spanners on subcubic graphs
- Shortest-path queries in static networks
- Path-fault-tolerant approximate shortest-path trees
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Approximating Shortest Paths in Graphs
- New pairwise spanners
- Improved approximation for the directed spanner problem
- Efficient vertex-label distance oracles for planar graphs
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Small stretch pairwise spanners and approximate \(D\)-preservers
- Automata, Languages and Programming
- Title not available (Why is that?)
- Vertex fault tolerant additive spanners
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
This page was built for publication: Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944530)
