Metraipolis › archive › dc_5fad02b68142
Towards Dynamic Top-$k$ Simple Shortest Paths — arXiv:2610.20062
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.20062
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T21:58:27.705Z
- SHA-256 of the archived text
1051c1b8ced76f292ab387a566349892ae7bd8bbabdedabf1d93ec41a58124e8- Stable URL of this page
https://metraipolis.com/documento/dc_5fad02b68142
How to cite
Towards Dynamic Top-$k$ Simple Shortest Paths — arXiv:2610.20062 — arXiv (en), https://arxiv.org/abs/2610.20062 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5fad02b68142 (Metraipolis archive dc_5fad02b68142, sha256 1051c1b8ced76f292ab387a566349892ae7bd8bbabdedabf1d93ec41a58124e8)
BibTeX
@misc{dc5fad02b68142,
title = {Towards Dynamic Top-$k$ Simple Shortest Paths — arXiv:2610.20062},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.20062},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5fad02b68142; sha256 1051c1b8ced76f292ab387a566349892ae7bd8bbabdedabf1d93ec41a58124e8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20062. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Computing the top-$k$ \textit{simple} shortest paths between two vertices of a graph, i.e., solving the P-KSSP problem, is a fundamental primitive in graph analytics. In modern scenarios, however, queries are rarely one-shot: parameters change as applications adapt their information needs, and recomputing a solution from scratch at every request quickly becomes a bottleneck. We study P-KSSP in a dynamic setting, focusing on changes of the parameter $k$: given a top-$k$ solution for a pair of vertices and a new value $k'$, the goal is to compute a top-$k'$ solution reusing the previously computed paths. Our approach rests on the \textit{pseudo-tree}, a compact representation of a collection of simple $s$--$t$ paths: we show that building it from an arbitrary, unstructured solution amounts to trie construction, and give two constructions running in time linear in the size of the collection. On top of it, we design UPD, a dynamic algorithm that updates a solution upon a change of $k$; we prove its correctness, analyze its complexity, and show that it is a general, solver-agnostic scheme, which starts from the paths alone, is parametric in the routine that generates candidate paths and combinable with known preprocessing techniques, as well as with an online pruning rule that we formalize. While a worst-case update is asymptotically comparable to recomputing from scratch, an extensive experimental evaluation shows that a variant of UPD is the fastest method in the large majority of tested configurations, often by a wide margin (with speedups over recomputation that grow with $k$ and $k'$ and exceed $60\times$), yielding a practical recipe for the configuration to deploy.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.20062 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:39:44.502Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).