arXiv Open Access 2025

Simpler and Faster Directed Low-Diameter Decompositions

Jason Li

Lihat Sumber

Abstrak

We present a simpler and faster algorithm for low-diameter decompositions on directed graphs, matching the $O(\log n\log\log n)$ loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to $O((m+n\log\log n)\log^2n)$.

Topik & Kata Kunci

cs.DS

Penulis (1)

Jason Li

Format Sitasi

APA MLA BibTeX

Li, J. (2025). Simpler and Faster Directed Low-Diameter Decompositions. https://arxiv.org/abs/2505.10244

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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