Metraipolis › archive › dc_7ea2a60cd3f5

Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets — arXiv:2610.12057

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.12057
License (as archived): CC0-1.0
Archived: 2026-10-09T06:36:25.960Z
SHA-256 of the archived text: f5cf7717610ed0db8c1c28eb41be39f3c6581fcac08b141ce622dcb005a305fd
Stable URL of this page: https://metraipolis.com/documento/dc_7ea2a60cd3f5

How to cite

Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets — arXiv:2610.12057 — arXiv (en), https://arxiv.org/abs/2610.12057 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7ea2a60cd3f5 (Metraipolis archive dc_7ea2a60cd3f5, sha256 f5cf7717610ed0db8c1c28eb41be39f3c6581fcac08b141ce622dcb005a305fd)

BibTeX

@misc{dc7ea2a60cd3f5,
  title = {Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets — arXiv:2610.12057},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.12057},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7ea2a60cd3f5; sha256 f5cf7717610ed0db8c1c28eb41be39f3c6581fcac08b141ce622dcb005a305fd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12057. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

While there have been many recent advances in getting better tradeoffs for directed distance structures such as hopsets, shortcut sets and distance preservers, most known algorithms are inefficient. In this work we provide three results: - Faster algorithms for directed $(1+\epsilon)$-hopsets, matching the state-of-the-art size/hopbound trade-offs of Bernstein & Wein [SODA23]. Our algorithm is first designed for DAGs and then extended to general graphs (up to $n^{o(1)}$ factors) using the recent DAG projection result of Haeupler, Jiang, and Saranurak [STOC26]. - Faster \textit{deterministic} algorithms for constructing shortcut sets, matching the state-of-the-art size/hopbound tradeoffs of Kogan & Parter [SODA22A]. - Using our improved directed hopset construction, we get significantly faster algorithms for computing source-wise distance preservers. This algorithm is based on speeding-up reductions of Kogan & Parter [SODA22B] by using certain structural properties of our hopsets.

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.12057 — 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-09T05:57:12.789Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).