4 papers
Bellman-Ford in Almost-Linear Time
Isaac M. Hair, George Z. Li, Jason Li +1
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time.
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
Isaac M. Hair, George Z. Li, Jason Li +1
We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1…
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, Jingxun Liang +3
In the static retrieval problem, a data structure must answer retrieval queries mapping a set of keys in a universe to -bit values. Information-theoretically, retrieva…
Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, Huacheng Yu +2
In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U…