New Separations and Reductions for Directed Hopsets and Preservers
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu
2025年份
2被引次数
3顶会引用
摘要
We study distance preservers, hopsets, and shortcut sets in n-node, m-edge directed graphs, and show improved bounds and new reductions for various settings for these problems.
问问这篇 Paper
问问你的智能体。
Lune 读过与它相关的顶会 Paper，每个回答都会注明依据哪几篇。
引用它的顶会 Paper3
- DAG Projections: Reducing Distance and Flow Problems to DAGsBernhard Haeupler, Yonggang Jiang, Thatchaphol SaranurakSTOC 2026 · 被引用 2 次
- Covering Approximate Shortest Paths with DAGsSepehr Assadi, Gary Hoppenworth, Nicole WeinSTOC 2025 · 被引用 1 次
- Reviving Thorup's Shortcut ConjectureAaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler 等STOC 2026 · 被引用 1 次
相关 Paper
- Having Hope in Hops: New Spanners, Preservers and Lower Bounds for HopsetsShimon Kogan, Merav ParterFOCS 2022 · 被引用 5 次
- Closing the Gap Between Directed Hopsets and Shortcut SetsAaron Bernstein, Nicole WeinSODA 2023 · 被引用 3 次
- Simpler and Higher Lower Bounds for Shortcut SetsVirginia Vassilevska Williams, Yinzhan Xu, Zixuan XuSODA 2024 · 被引用 2 次
- Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n BarrierGreg Bodwin, Gary HoppenworthFOCS 2023 · 被引用 2 次
- Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation ProductKevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan XuSODA 2022 · 被引用 6 次
