Results 2401 - 2410 of 23934
Letong Wang is a fifth-year PhD student in the Computer Science and Engineering (CSE) Department at the University of California, Riverside (UCR). Her research lies at the intersection of multi-core parallel computing and graph algorithms, focusing on...
Hongbo Kang is a PhD candidate in computer science at Tsinghua University, and his research interests include designing theoretically and practically efficient parallel algorithms, especially on new hardware. His previous research primarily focused on...
We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an n−vertex planar graph G=(V, E) undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a (1+ϵ)−approximate dynamic algorithm that supports edge updates and distance queries in n^{o(1)} time, for any 1/poly(logn) < ϵ < 1. Our result is a significant improvement over the best previously known bound of ~O(\sqrt{n}) on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a Ω(\sqrt{n}) conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].
The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(mn)$ time on a graph with m edges and n vertices. A recent breakthrough algorithm by Fineman [Fin24] takes $\tilde{O}(m n^{8/9})$ randomized time. We present an $\tilde{O}(m n^{4/5} randomized time algorithm building on ideas from [Fin24].