On the all-pairs-shortest-path problem in unweighted undirected graphs.
From MaRDI portal
Publication:960518
DOI10.1006/jcss.1995.1078zbMath1295.05240OpenAlexW2058426370MaRDI QIDQ960518
Publication date: 21 December 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1078
Related Items
Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Solving the all-pairs-shortest-length problem on chordal bipartite graphs ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Improved algorithm for all pairs shortest paths ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Eccentricity queries and beyond using hub labels ⋮ On computing the diameter of real-world undirected graphs ⋮ The diameter of AT‐free graphs ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ Streaming graph computations with a helpful advisor ⋮ Path Laplacian matrices: introduction and application to the analysis of consensus in networks ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Shortest distances as enumeration problem ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ On dynamic shortest paths problems ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ Approximation bounds for Black Hole Search problems ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ On minimum witnesses for Boolean matrix multiplication ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Algebraic methods in the congested clique ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ A spectral approach to the shortest path problem ⋮ TWO ALGORITHMS FOR FAST INCREMENTAL TRANSITIVE CLOSURE OF SPARSE FUZZY BINARY RELATIONS ⋮ Unnamed Item ⋮ Solving path problems on the GPU ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Parameterized complexity of diameter ⋮ Unnamed Item ⋮ Some optimization problems on weak-bisplit graphs ⋮ A selected tour of the theory of identification matrices ⋮ Percolation centrality via Rademacher Complexity ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computationally efficient sup-t transitive closure for sparse fuzzy binary relations ⋮ The birth of geometry in exponential random graphs
