{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:49Z","timestamp":1781028289410,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800928","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2266-2277","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DAG Projections: Reducing Distance and Flow Problems to DAGs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"INSAIT at Sofia University St. Kliment Ohridski, Sofia, Bulgaria"},{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8485-6676","authenticated-orcid":false,"given":"Yonggang","family":"Jiang","sequence":"additional","affiliation":[{"name":"MPI-INF, Saarbrucken, Germany"},{"name":"Saarland University, Saarbrucken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8386-7168","authenticated-orcid":false,"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"A general approach to online network optimization problems","volume":"2","author":"Alon Noga","year":"2006","unstructured":"Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. 2006. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG) 2, 4 ( 2006 ), 640-660.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. In ESA (LIPIcs, Vol. 308 )","volume":"13","author":"Ashvinkumar Vikrant","year":"2024","unstructured":"Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin-Hao Su. 2024. Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. In ESA (LIPIcs, Vol. 308 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 13 : 1-13 : 15.","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.180"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718298"},{"key":"e_1_3_2_1_5_1","unstructured":"Anonymous Authors. 2025. Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers. ( 2025 ). Manuscript.."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"e_1_3_2_1_7_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 20-1.","author":"Bartal Yair","year":"2019","unstructured":"Yair Bartal, Nova Fandina, and Ofer Neiman. 2019. Covering Metric Spaces by Few Trees. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 20-1."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00026"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00123"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein Danupon Nanongkai and Christian Wulf-Nilsen. 2025. Negative-Weight Single-Source Shortest Paths in Near-Linear Time. Commun. ACM 68 2 ( 2025 ) 87-94. First anounce at FOCS' 22..","DOI":"10.1145\/3631536"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch7"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.39"},{"key":"e_1_3_2_1_13_1","first-page":"515","article-title":"Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!","author":"Bringmann Karl","year":"2023","unstructured":"Karl Bringmann, Alejandro Cassis, and Nick Fischer. 2023. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!. In FOCS. IEEE, 515-538.","journal-title":"FOCS. IEEE"},{"key":"e_1_3_2_1_14_1","first-page":"336","article-title":"Eficient construction of directed hopsets and parallel approximate shortest paths","author":"Cao Nairen","year":"2020","unstructured":"Nairen Cao, Jeremy T. Fineman, and Katina Russell. 2020. Eficient construction of directed hopsets and parallel approximate shortest paths. In STOC. ACM, 336-349.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00089"},{"key":"e_1_3_2_1_16_1","first-page":"612","article-title":"Maximum Flow and Minimum-Cost Flow in AlmostLinear Time","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in AlmostLinear Time. In FOCS. IEEE, 612-623.","journal-title":"FOCS. IEEE"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/110844970"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605"},{"key":"e_1_3_2_1_19_1","volume-title":"Sparse source-wise and pair-wise distance preservers","author":"Coppersmith Don","unstructured":"Don Coppersmith and Michael Elkin. 2005. Sparse source-wise and pair-wise distance preservers. In SODA. SIAM, 660-669."},{"key":"e_1_3_2_1_20_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 60-1.","author":"Dalirrooyfard Mina","year":"2021","unstructured":"Mina Dalirrooyfard and Jenny Kaufmann. 2021. Approximation Algorithms for Min-Distance Problems in DAGs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 60-1."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_1_22_1","unstructured":"Arnold Filtser. 2025. Stochastic Embedding of Digraphs into DAGs. arXiv preprint arXiv:2509.23458 ( 2025 )."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777419"},{"key":"e_1_3_2_1_24_1","volume-title":"Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 52-1.","author":"He Zhiyang","year":"2021","unstructured":"Zhiyang He, Jason Li, and Magnus Wahlstr\u00f6m. 2021. Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 52-1."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.150"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.55"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/79"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_1_31_1","volume-title":"European Symposium on Algorithms. Springer, 774-785","author":"R\u00e4cke Harald","year":"2014","unstructured":"Harald R\u00e4cke and Chintan Shah. 2014. Improved guarantees for tree cut sparsiifers. In European Symposium on Algorithms. Springer, 774-785."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.17"},{"key":"e_1_3_2_1_33_1","first-page":"321","article-title":"Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances","author":"Rozhon V\u00e1clav","year":"2023","unstructured":"V\u00e1clav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic. 2023. Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. In STOC. ACM, 321-334.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00120"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:14Z","timestamp":1781027774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":35,"alternative-id":["10.1145\/3798129.3800928","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800928","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}