Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers

Shimon Kogan; Merav Parter

doi:10.1137/1.9781611977554.ch9

SODA2023顶会

Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers

Shimon Kogan, Merav Parter

DOI 出版方

2023年份

1被引次数

2顶会引用

摘要

For an n-vertex m-edge digraph G, a D-shortcut is a small set H of directed edges taken from the transitive closure of G, satisfying that the diameter of G ∪ H is at most D. In a sequence of works [Kogan and Parter, SODA 2022 & ICALP 2022] provided shortcut algorithms with improved diameter vs. size tradeoffs. In this paper, we present faster and unified shortcut algorithms for general digraphs. These algorithms also yield improved tradeoffs for the family of bounded-width DAGs. We show: