Certified shortcuts are precisely the ones constructible in near-linear time, and no almost-linear-size certified shortcut can reduce diameter below n^{1/4-o(1)}.
Faster and Unified Algorithms for Diameter Re- ducing Shortcuts and Minimum Chain Covers
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3verdicts
UNVERDICTED 3representative citing papers
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
A greedy algorithm matches recent optimal size/hopbound tradeoffs for shortcut sets and receives a new existential optimality proof for matching hopsets up to logarithmic factors.
citing papers explorer
-
Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
Certified shortcuts are precisely the ones constructible in near-linear time, and no almost-linear-size certified shortcut can reduce diameter below n^{1/4-o(1)}.
-
Multi-Source Reachability in Near-Optimal Time
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
-
Greedy Algorithms for Shortcut Sets and Hopsets
A greedy algorithm matches recent optimal size/hopbound tradeoffs for shortcut sets and receives a new existential optimality proof for matching hopsets up to logarithmic factors.