On the all-pairs-shortest-path problem in unweighted undirected graphs.
From MaRDI portal
(Redirected from Publication:960518)
Recommendations
- All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- STACS 2005
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- All pairs shortest paths for graphs with small integer length edges
Cited in
(67)- Path Laplacian matrices: introduction and application to the analysis of consensus in networks
- Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
- A survey of the all-pairs shortest paths problem and its variants in graphs
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- Improved algorithm for all pairs shortest paths
- Regularity lemmas and combinatorial algorithms
- STACS 2005
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
- scientific article; zbMATH DE number 2119672 (Why is no real title available?)
- Faster all-pairs shortest paths via circuit complexity
- Improved distance sensitivity oracles with subcubic preprocessing time
- Fully dynamic all pairs shortest paths with real edge weights
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Solving the all-pairs-shortest-length problem on chordal bipartite graphs
- Computationally efficient sup-t transitive closure for sparse fuzzy binary relations
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- On the Shoshan-Zwick algorithm for the all-pairs shortest path problem
- A spectral approach to the shortest path problem
- Approximation bounds for Black Hole Search problems
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- Leanness computation: small values and special graph classes
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Networks cannot compute their diameter in sublinear time
- Solving path problems on the GPU
- The diameter of AT‐free graphs
- A new approach to all-pairs shortest paths on real-weighted graphs
- Shortest distances as enumeration problem
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- The birth of geometry in exponential random graphs
- scientific article; zbMATH DE number 7561506 (Why is no real title available?)
- Two algorithms for fast incremental transitive closure of sparse fuzzy binary relations
- All-pairs shortest paths algorithm for high-dimensional sparse graphs
- Some optimization problems on weak-bisplit graphs
- A branch-checking algorithm for all-pairs shortest paths
- Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
- Eccentricity queries and beyond using hub labels
- Parameterized complexity of diameter
- Some results on approximate 1-median selection in metric spaces
- On compact representations of all-pairs-shortest-path-distance matrices
- All-pairs bottleneck paths in vertex weighted graphs
- On dynamic shortest paths problems
- Shortest-Path Reconstruction Algorithms
- scientific article; zbMATH DE number 3922691 (Why is no real title available?)
- An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
- Reconstructing shortest paths
- Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems
- Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- New algorithms for all pairs approximate shortest paths
- From circuit complexity to faster all-pairs shortest paths
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- Optimal computation of shortest paths on doubly convex bipartite graphs
- On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices
- Using weighted graphs features for fast searching their parameters
- Algorithm design for tensor units
- Improved time bounds for all pairs non-decreasing paths in general digraphs
- A selected tour of the theory of identification matrices
- On minimum witnesses for Boolean matrix multiplication
- A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs
- All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- On computing the diameter of real-world undirected graphs
- Percolation centrality via Rademacher Complexity
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
This page was built for publication: On the all-pairs-shortest-path problem in unweighted undirected graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q960518)
