arXiv preprint ·
Partially Dynamic Algorithms for Single-Source Temporal Paths
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with $n$ vertices. For the incremental scenario where updates are arc insertions, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the total number of arcs added to the arc-less graph. For the decremental scenario where updates are arc removals, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the number of arcs in the graph upon its initialization. We also consider earliest-arrival queries with an arbitrary departure-time threshold and develop an incremental algorithm with $O(n+Δ_s m\log m)$ total update time, $O(\log m)$ query time, and $O(n+m)$ space, where $Δ_s$ is the number of distinct departure times of arcs leaving the source. All of our algorithms are also capable of reporting an earliest arrival path from the source to the queried vertex $v$ in constant time per edge once the earliest arrival time at $v$ is known. We complement our positive results with conditional lower bounds based on the Online Boolean Matrix-Vector Multiplication conjecture (a.k.a. OMv conjecture). For both the incremental and the decremental scenarios, we show the non-existence of an algorithm with $O(n^{1-\varepsilon})$ amortized update time and $O(n^{2-\varepsilon})$ amortized query time, even if the algorithm is randomized and latencies on the arcs are uniform. For arbitrary departure-time queries, we also establish an OMv-based conditional lower bound showing that our incremental algorithm is optimal up to logarithmic factors on dense temporal graphs. Thus, efficient total running time is essentially the best outcome we can get. Our conditional lower bounds hold also for the case of undirected temporal graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Quadratic-Time Barriers from Self-Referential SAT
Sublinear Metric Distortion for Matching
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.