All-Pairs Almost Shortest Paths
From MaRDI portal
Publication:4943891
DOI10.1137/S0097539797327908zbMath0948.05047OpenAlexW2156047991MaRDI QIDQ4943891
Uri Zwick, Shay Halperin, Dorit Dor
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539797327908
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (57)
On resilient graph spanners ⋮ Thorup-Zwick emulators are universally optimal hopsets ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Spanners for bounded tree-length graphs ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Approximate distance oracles for graphs with dense clusters ⋮ On additive spanners in weighted graphs with local error ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ When distributed computation is communication expensive ⋮ Vertex fault tolerant additive spanners ⋮ Improved weighted additive spanners ⋮ Relaxed spanners for directed disk graphs ⋮ Approximate shortest paths in weighted graphs ⋮ New pairwise spanners ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ Unnamed Item ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ An all-pairs shortest path algorithm for bipartite graphs ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Compact roundtrip routing with topology-independent node names ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Shortest-path queries in static networks ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ Close to linear space routing schemes ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ On the power of BFS to determine a graph's diameter ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Localized and compact data-structure for comparability graphs ⋮ Fast approximate shortest paths in the congested clique ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Edge-disjoint spanners of complete graphs and complete digraphs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners ⋮ Distance Labeling for Permutation Graphs ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
This page was built for publication: All-Pairs Almost Shortest Paths
