{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:49Z","timestamp":1781031409197,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":48,"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.3800861","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1528-1539","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar Length-Constrained Minimum Spanning Trees"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0862-3715","authenticated-orcid":false,"given":"D Ellis","family":"Hershkowitz","sequence":"first","affiliation":[{"name":"Brown University, Providence, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5611-9863","authenticated-orcid":false,"given":"Richard Z","family":"Huang","sequence":"additional","affiliation":[{"name":"Brown University, Providence, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJOR.2011.01.051"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.1999.tb00176.x"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ORL.2004.05.005"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.180"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00130-9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1425487"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2024.41"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2024.42"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365452"},{"key":"e_1_3_2_1_13_1","volume-title":"International Symposium on Theoretical Aspects of Computer Science (STACS). 238\u2013248","author":"Chimani Markus","year":"2015","unstructured":"Markus Chimani and Joachim Spoerhase. 2015. Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In International Symposium on Theoretical Aspects of Computer Science (STACS). 238\u2013248."},{"key":"e_1_3_2_1_14_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJOR.2017.08.017"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2025.106581"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00056"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Zachary Friggstad and Ramin Mousavi. 2023. An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. In International Colloquium on Automata Languages and Programming (ICALP). 63\u20131. https:\/\/doi.org\/10.1145\/3734525 10.1145\/3734525","DOI":"10.1145\/3734525"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SWAT.2024.23"},{"key":"e_1_3_2_1_20_1","unstructured":"Michael R Garey and David S Johnson. 2002. Computers and intractability. 29 wh freeman New York."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451098"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316349"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649689"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585202"},{"key":"e_1_3_2_1_25_1","unstructured":"Bernhard Haeupler D Ellis Hershkowitz and Zihan Tan. 2023. Parallel greedy spanners. arXiv preprint arXiv:2304.08892."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00102"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451053"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00121"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520026"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-007-9013-X"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445718"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.25"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-006-1305-Z"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10878-014-9774-5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00111-0"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2008.01.004"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3681791"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0930"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/050629665"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646142"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505243"},{"key":"e_1_3_2_1_46_1","unstructured":"Thomas Rothvo\u00df. 2011. Directed steiner tree and the lasserre hierarchy. arXiv preprint arXiv:1111.5473."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523690"},{"key":"e_1_3_2_1_48_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2, 59\u201363","author":"Zosin Leonid","year":"2002","unstructured":"Leonid Zosin and Samir Khuller. 2002. On directed Steiner trees. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2, 59\u201363."}],"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.3800861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:57:35Z","timestamp":1781027855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":48,"alternative-id":["10.1145\/3798129.3800861","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800861","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"}}]}}