arXiv Open Access 2024

Fully Dynamic Shortest Paths in Sparse Digraphs

Adam Karczmarz Piotr Sankowski

Lihat Sumber

Abstrak

We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with $\tilde{O}(mn^{4/5})$ worst-case update time processing arbitrary $s,t$-distance queries in $\tilde{O}(n^{4/5})$ time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.

Topik & Kata Kunci

cs.DS

Penulis (2)

Adam Karczmarz

Piotr Sankowski

Format Sitasi

APA MLA BibTeX

Karczmarz, A., Sankowski, P. (2024). Fully Dynamic Shortest Paths in Sparse Digraphs. https://arxiv.org/abs/2408.14406

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓