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

Cited In (28)

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?)
Improved Approximation for the Directed Spanner Problem
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
Small Stretch Pairwise Spanners and Approximate $D$-Preservers
Title not available (Why is that?)
Distributed distance computation and routing with small messages
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
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
Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
Approximating Shortest Paths in Graphs
New pairwise spanners
Efficient vertex-label distance oracles for planar graphs
Improved NP-hardness results for the minimum $t$-spanner problem on bounded-degree graphs
Distributed Spanner Approximation
Title not available (Why is that?)
Path-Fault-Tolerant Approximate Shortest-Path Trees
Vertex fault tolerant additive spanners
Transitive-Closure Spanners: A Survey

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944530)