Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
From MaRDI portal
Publication:4268701
DOI10.1137/S0097539796303421zbMath0926.68093OpenAlexW1988067232MaRDI QIDQ4268701
Donald D. Aingworth, Chandra Chekuri, Piotr Indyk, Rajeev Motwani
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796303421
Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Parallel algorithms in computer science (68W10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (67)
On resilient graph spanners ⋮ Thorup-Zwick emulators are universally optimal hopsets ⋮ Source-wise round-trip spanners ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ Spanners for bounded tree-length graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Equality of opportunity and integration in social networks ⋮ \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Deterministic improved round-trip spanners ⋮ Approximate distance oracles for graphs with dense clusters ⋮ On additive spanners in weighted graphs with local error ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Demand-aware network designs of bounded degree ⋮ Vertex fault tolerant additive spanners ⋮ Improved weighted additive spanners ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem ⋮ Approximate shortest paths in weighted graphs ⋮ New pairwise spanners ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ Multi-priority graph sparsification ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ Fast approximation of betweenness centrality through sampling ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Discovery of network properties with all-shortest-paths queries ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Improved approximation algorithms for maximum lifetime problems in wireless networks ⋮ Diameter determination on restricted graph families ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ Approximate proof-labeling schemes ⋮ A fast algorithm for source-wise round-trip spanners ⋮ 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 ⋮ Parameterized complexity of diameter ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Fast approximate shortest paths in the congested clique ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Distance-Preserving Graph Contractions ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Bounded degree spanners of the hypercube ⋮ Distance-Preserving Graph Contractions ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
Uses Software
This page was built for publication: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
