On the public citation graph

All-Pairs Shortest Paths with Real Weights in O(n 3/log n) Time

0 signed · 66 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jcss.1995.1065openalex-snapshot
Clique Partitions, Graph Compression and Speeding-Up Algorithms
inferredcites →https://doi.org/10.1006/jcss.1995.1078openalex-snapshot
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
inferredcites →https://doi.org/10.1006/jcss.1997.1385openalex-snapshot
All Pairs Shortest Paths for Graphs with Small Integer Length Edges
inferredcites →https://doi.org/10.1006/jcss.1997.1388openalex-snapshot
On the Exponent of the All Pairs Shortest Path Problem
inferredcites →https://doi.org/10.1007/978-1-4612-1098-6openalex-snapshot
Computational Geometry
inferredcites →https://doi.org/10.1007/978-1-4842-7077-6_3openalex-snapshot
Introduction to Algorithms
inferredcites →https://doi.org/10.1007/978-3-540-27798-9_31openalex-snapshot
A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application
inferredcites →https://doi.org/10.1007/978-3-540-30140-0_54openalex-snapshot
Fast Sparse Matrix Multiplication
inferredcites →https://doi.org/10.1007/978-3-540-30551-4_78openalex-snapshot
A Slightly Improved Sub-cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths
inferredcites →https://doi.org/10.1007/bf02165411openalex-snapshot
Gaussian elimination is not optimal
inferredcites →https://doi.org/10.1007/s00453-005-1199-1openalex-snapshot
A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths
inferredcites →https://doi.org/10.1016/0020-0190(91)90071-oopenalex-snapshot
Computing dominances in En
inferredcites →https://doi.org/10.1016/0020-0190(92)90200-fopenalex-snapshot
A new upper bound on the complexity of the all pairs shortest path problem
inferredcites →https://doi.org/10.1016/j.ipl.2004.05.006openalex-snapshot
Improved algorithm for all pairs shortest paths
inferredcites →https://doi.org/10.1016/j.ipl.2005.08.008openalex-snapshot
An time algorithm for the all-pairs shortest path problem
inferredcites →https://doi.org/10.1016/s0304-3975(03)00402-xopenalex-snapshot
A new approach to all-pairs shortest paths on real-weighted graphs
inferredcites →https://doi.org/10.1016/s0747-7171(08)80013-2openalex-snapshot
Matrix multiplication via arithmetic progressions
inferredcites →https://doi.org/10.1080/00207169008803814openalex-snapshot
A more efficient algorithm for the min-plus multiplication
inferredcites →https://doi.org/10.1109/sffcs.1999.814635openalex-snapshot
All pairs shortest paths in undirected graphs with integer weights
inferredcites →https://doi.org/10.1137/0205006openalex-snapshot
New Bounds on the Complexity of the Shortest Path Problem
inferredcites →https://doi.org/10.1137/s0097539702419650openalex-snapshot
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
inferredcites →https://doi.org/10.1145/1077464.1077466openalex-snapshot
Fast sparse matrix multiplication
inferredcites →https://doi.org/10.1145/276698.276764openalex-snapshot
Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators
inferredcites →https://doi.org/10.1145/567112.567114openalex-snapshot
All pairs shortest paths using bridging sets and rectangular matrix multiplication
inferredcites →https://doi.org/10.2307/2008200openalex-snapshot
Computational Geometry--An Introduction.
inferredcites →https://doi.org/10.48550/arxiv.cs/0304018openalex-snapshot
Quasiconvex Analysis of Backtracking Algorithms
inferredcites →https://doi.org/10.5555/1109557.1109614openalex-snapshot
All-pairs shortest paths for unweighted undirected graphs in o(mn) time

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11786986_24openalex-snapshot
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
inferred← citeshttps://doi.org/10.1007/11818175_18openalex-snapshot
Fast Algorithms for the Free Riders Problem in Broadcast Encryption
inferred← citeshttps://doi.org/10.1007/11841036_17openalex-snapshot
Necklaces, Convolutions, and X + Y
inferred← citeshttps://doi.org/10.1007/11841036_38openalex-snapshot
An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
inferred← citeshttps://doi.org/10.1007/978-3-319-77510-4_6openalex-snapshot
Practical Algorithms for the All-Pairs Shortest Path Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_10openalex-snapshot
A New Combinatorial Approach for Sparse Graph Problems
inferred← citeshttps://doi.org/10.1007/978-3-540-73437-6_4openalex-snapshot
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
inferred← citeshttps://doi.org/10.1007/978-3-642-31155-0_12openalex-snapshot
An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
inferred← citeshttps://doi.org/10.1007/s00453-007-9063-0openalex-snapshot
An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path
inferred← citeshttps://doi.org/10.1007/s00453-007-9128-0openalex-snapshot
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
inferred← citeshttps://doi.org/10.1016/j.jda.2013.03.005openalex-snapshot
Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
inferred← citeshttps://doi.org/10.1016/j.jda.2016.09.001openalex-snapshot
An O(n3loglogn/log2n) time algorithm for all pairs shortest paths
inferred← citeshttps://doi.org/10.1016/j.neucom.2017.01.121openalex-snapshot
WordNet2Vec: Corpora agnostic word vectorization method
inferred← citeshttps://doi.org/10.1109/focs.2006.29openalex-snapshot
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths
inferred← citeshttps://doi.org/10.1109/focs.2013.58openalex-snapshot
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
inferred← citeshttps://doi.org/10.1109/icacte66284.2025.11412126openalex-snapshot
3SUM Problem Exploration
inferred← citeshttps://doi.org/10.1109/iciccs51141.2021.9432275openalex-snapshot
An Extensive Review of Shortest Path Problem Solving Algorithms
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch87openalex-snapshot
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
inferred← citeshttps://doi.org/10.1137/1.9781611975031.33openalex-snapshot
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ ( n 5/3 ) Time
inferred← citeshttps://doi.org/10.1145/1132516.1132550openalex-snapshot
Finding a maximum weight triangle in n 3-Δ time, with applications
inferred← citeshttps://doi.org/10.1145/1198513.1198518openalex-snapshot
Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
inferred← citeshttps://doi.org/10.1145/1250790.1250876openalex-snapshot
All-pairs bottleneck paths for general graphs in truly sub-cubic time
inferred← citeshttps://doi.org/10.1145/1250790.1250877openalex-snapshot
More algorithms for all-pairs shortest paths in weighted graphs
inferred← citeshttps://doi.org/10.1145/1328438.1328460openalex-snapshot
Subcubic algorithms for recursive state machines
inferred← citeshttps://doi.org/10.1145/1328897.1328460openalex-snapshot
Subcubic algorithms for recursive state machines
inferred← citeshttps://doi.org/10.1145/1644015.1644035openalex-snapshot
Computing rank-convolutions with a mask
inferred← citeshttps://doi.org/10.1145/1798596.1798597openalex-snapshot
Finding heaviest H -subgraphs in real weighted graphs, with applications
inferred← citeshttps://doi.org/10.1145/3186893openalex-snapshot
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
inferred← citeshttps://doi.org/10.1145/3229710.3229730openalex-snapshot
Efficient Parallel All-Pairs Shortest Paths Algorithm for Complex Graph Analysis
inferred← citeshttps://doi.org/10.14778/3551793.3551862openalex-snapshot
Optimizing differentially-maintained recursive queries on dynamic graphs
inferred← citeshttps://doi.org/10.1515/ausi-2016-0002openalex-snapshot
A survey of the all-pairs shortest paths problem and its variants in graphs
inferred← citeshttps://doi.org/10.1613/jair.3509openalex-snapshot
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
inferred← citeshttps://doi.org/10.26021/8920openalex-snapshot
Sub-cubic Time Algorithm for the k-disjoint Maximum subarray Problem
inferred← citeshttps://doi.org/10.35376/10324/16003openalex-snapshot
Parallel approaches to shortest-path problems for multilevel heterogeneous computing
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2021.3openalex-snapshot
0-1 Integer Linear Programming with a Linear Number of Constraints
inferred← citeshttps://doi.org/10.48550/arxiv.1911.06132openalex-snapshot
$\{-1,0,1\}$-APSP and (min,max)-Product Problems
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0609009openalex-snapshot
Finding heaviest H-subgraphs in real weighted graphs, with applications
inferred← citeshttps://doi.org/10.5555/1109557.1109614openalex-snapshot
All-pairs shortest paths for unweighted undirected graphs in o(mn) time
inferred← citeshttps://doi.org/10.5555/1283383.1283488openalex-snapshot
All-pairs bottleneck paths in vertex weighted graphs
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.