An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
Ryan , year =
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 6years
2026 6verdicts
UNVERDICTED 6roles
background 1polarities
background 1representative citing papers
Node-weighted triangle detection can be solved in optimal O(MM(n)) time with a simpler algorithm than previous work.
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
Achieves (2k/3)-approximation for girth in weighted graphs in Õ(m + n^{1+2/k}) time for every k≥2, improving prior partial results, plus new fine-grained lower bounds for unweighted girth approximation.
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
Deterministic O(n^{2.686})-time algorithm for Monotone Min-Plus Product and n^{1.5+o(1)}-time algorithm for Monotone Min-Plus Convolution, derandomizing prior randomized results.
citing papers explorer
-
Warm-Starting All-Pairs Shortest Paths with Predictions
An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
-
Node-Weighted Triangles: Faster and Simpler
Node-weighted triangle detection can be solved in optimal O(MM(n)) time with a simpler algorithm than previous work.
-
Undirected Replacement Paths: Dual Fault Reduces to Single Source
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
-
Tighter bounds for weighted and unweighted shortest cycle approximation
Achieves (2k/3)-approximation for girth in weighted graphs in Õ(m + n^{1+2/k}) time for every k≥2, improving prior partial results, plus new fine-grained lower bounds for unweighted girth approximation.
-
Revisiting Diameter in Directed Graphs
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
-
Deterministic Monotone Min-Plus Product and Convolution
Deterministic O(n^{2.686})-time algorithm for Monotone Min-Plus Product and n^{1.5+o(1)}-time algorithm for Monotone Min-Plus Convolution, derandomizing prior randomized results.