On the public citation graph

An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

0 signed · 64 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.1007/bf01386390openalex-snapshot
A note on two problems in connexion with graphs
inferredcites →https://doi.org/10.1007/bfb0022539openalex-snapshot
An 0(n 2 lognloglogn) expected time algorithm for the all shortest distance problem
inferredcites →https://doi.org/10.1016/0166-218x(85)90059-9openalex-snapshot
The shortest-path problem for graphs with random arc-lengths
inferredcites →https://doi.org/10.1063/1.3034322openalex-snapshot
An Introduction to Probability Theory and Its Applications, Vol. 2
inferredcites →https://doi.org/10.1137/0202004openalex-snapshot
A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
inferredcites →https://doi.org/10.1137/0205006openalex-snapshot
New Bounds on the Complexity of the Shortest Path Problem
inferredcites →https://doi.org/10.1137/0206050openalex-snapshot
A Note on Spira’s Algorithm for the All-Pairs Shortest-Path Problem
inferredcites →https://doi.org/10.1137/0212039openalex-snapshot
A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
inferredcites →https://doi.org/10.1145/367766.368168openalex-snapshot
Algorithm 97: Shortest path
inferredcites →https://doi.org/10.1287/mnsc.6.2.187openalex-snapshot
On the Shortest Route Through a Network

What points at this work

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

inferred← citeshttps://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferred← citeshttps://doi.org/10.1002/(sici)1098-2418(200001)16:1<33::aid-rsa3>3.0.co;2-0openalex-snapshot
Average-case complexity of shortest-paths problems in the vertex-potential model
inferred← citeshttps://doi.org/10.1002/9781118033104.ch11openalex-snapshot
Graph Algorithms
inferred← citeshttps://doi.org/10.1006/jagm.1998.0937openalex-snapshot
Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
inferred← citeshttps://doi.org/10.1007/11611257_14openalex-snapshot
Constructing Interference-Minimal Networks
inferred← citeshttps://doi.org/10.1007/3-540-45643-0_10openalex-snapshot
Experimental Evaluation of a New Shortest Path Algorithm
inferred← citeshttps://doi.org/10.1007/3-540-50728-0_51openalex-snapshot
An efficient parallel algorithm for the all pairs shortest path problem
inferred← citeshttps://doi.org/10.1007/3-540-55121-2_20openalex-snapshot
A new upper bound on the complexity of the all pairs shortest path problem
inferred← citeshttps://doi.org/10.1007/3-540-60313-1_143openalex-snapshot
On the all-pairs shortest path algorithm of Moffat and Takaoka
inferred← citeshttps://doi.org/10.1007/3-540-61310-2_8openalex-snapshot
Finding real-valued single-source shortest paths in o(n 3) expected time
inferred← citeshttps://doi.org/10.1007/3-540-62559-3_29openalex-snapshot
Shortest path algorithms for nearly acyclic directed graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-13075-0_4openalex-snapshot
Average-Case Complexity of the Min-Sum Matrix Product Problem
inferred← citeshttps://doi.org/10.1007/978-3-322-89113-6_5openalex-snapshot
Graphen und Graph-Algorithmen
inferred← citeshttps://doi.org/10.1007/978-3-322-91882-6_5openalex-snapshot
Graphen und Graph-Algorithmen
inferred← citeshttps://doi.org/10.1007/978-3-322-92105-5_5openalex-snapshot
Graphen und Graph-Algorithmen
inferred← citeshttps://doi.org/10.1007/978-3-540-27798-9_31openalex-snapshot
A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application
inferred← citeshttps://doi.org/10.1007/978-3-540-74205-0_49openalex-snapshot
Key Point Based Data Analysis Technique
inferred← citeshttps://doi.org/10.1007/978-3-642-04802-9_11openalex-snapshot
Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-17461-2_16openalex-snapshot
A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time
inferred← citeshttps://doi.org/10.1007/978-3-7091-9076-0_11openalex-snapshot
Probabilistic Analysis of Graph Algorithms
inferred← citeshttps://doi.org/10.1007/bf01190847openalex-snapshot
All-pairs shortest paths and the essential subgraph
inferred← citeshttps://doi.org/10.1007/s10878-012-9550-3openalex-snapshot
A simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90200-fopenalex-snapshot
A new upper bound on the complexity of the all pairs shortest path problem
inferred← citeshttps://doi.org/10.1016/0895-7177(96)00006-4openalex-snapshot
Computation of shortest path in cellular automata
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50015-1openalex-snapshot
Graph Algorithms
inferred← citeshttps://doi.org/10.1016/j.comgeo.2007.06.004openalex-snapshot
Constructing minimum-interference networks
inferred← citeshttps://doi.org/10.1016/j.dam.2011.02.007openalex-snapshot
Average update times for fully-dynamic all-pairs shortest paths
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.09.008openalex-snapshot
Average-case complexity of the min-sum matrix product problem
inferred← citeshttps://doi.org/10.1016/j.trb.2016.11.014openalex-snapshot
A cooperative game approach to cost allocation in a rapid-transit network
inferred← citeshttps://doi.org/10.1016/s0196-6774(03)00046-4openalex-snapshot
Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
inferred← citeshttps://doi.org/10.1016/s0196-6774(03)00076-2openalex-snapshot
Δ-stepping: a parallelizable shortest path algorithm
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00613-8openalex-snapshot
Improved shortest path algorithms for nearly acyclic graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00292-2openalex-snapshot
Shortest path algorithms for nearly acyclic directed graphs
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)00313-5openalex-snapshot
Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)81018-1openalex-snapshot
The Reverse Problem of Range Query
inferred← citeshttps://doi.org/10.1109/71.762814openalex-snapshot
Minimizing the maximum delay for reaching consensus in quorum-based mutual exclusion schemes
inferred← citeshttps://doi.org/10.1109/focs.2010.69openalex-snapshot
All-Pairs Shortest Paths in O(n²) Time with High Probability
inferred← citeshttps://doi.org/10.1109/focs.2013.81openalex-snapshot
A Forward-Backward Single-Source Shortest Paths Algorithm
inferred← citeshttps://doi.org/10.1109/ijcnn.1991.170517openalex-snapshot
Systolic mapping of inference network for the all-pair shortest path problem
inferred← citeshttps://doi.org/10.1109/nswctc.2010.164openalex-snapshot
A Link Importance Evaluation Method Based on the Characteristic of Network Communication
inferred← citeshttps://doi.org/10.1109/tpami.2011.121openalex-snapshot
Fast Inference with Min-Sum Matrix Product
inferred← citeshttps://doi.org/10.1137/140970975openalex-snapshot
A Forward-Backward Single-Source Shortest Paths Algorithm
inferred← citeshttps://doi.org/10.1137/s0097539702419650openalex-snapshot
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
inferred← citeshttps://doi.org/10.1145/2508028.2505988openalex-snapshot
All-pairs shortest paths in O ( n 2 ) time with high probability
inferred← citeshttps://doi.org/10.1201/9781315139975-1openalex-snapshot
Parallel Computations in *-Semirings
inferred← citeshttps://doi.org/10.1349/ddlp.2780openalex-snapshot
Exact and approximation algorithms for network flow and disjoint-path problems.
inferred← citeshttps://doi.org/10.22028/d291-25720openalex-snapshot
Design and analysis of sequential and parallel single-source shortest-paths algorithms
inferred← citeshttps://doi.org/10.22028/d291-25863openalex-snapshot
Average-case complexity of shortest-paths problems
inferred← citeshttps://doi.org/10.25911/5d611c34235c0openalex-snapshot
Graphical models for inference and learning in computer vision
inferred← citeshttps://doi.org/10.26493/1855-3974.2467.497openalex-snapshot
Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
inferred← citeshttps://doi.org/10.4304/jnw.6.3.462-469openalex-snapshot
Finding the Most Vital Link with Respect to the Characteristic of Network Communication
inferred← citeshttps://doi.org/10.48550/arxiv.0910.3301openalex-snapshot
Faster Algorithms for Max-Product Message-Passing
inferred← citeshttps://doi.org/10.48550/arxiv.1105.3770openalex-snapshot
All-Pairs Shortest Paths in $O(n^2)$ time with high probability
inferred← citeshttps://doi.org/10.5555/365411.365449openalex-snapshot
Fast approximation of centrality
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.