{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:42Z","timestamp":1781077722626,"version":"3.54.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSERC Discovery"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"\n We present a\n \n \\(O(\\log k)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation for both the edge-weighted and node-weighted versions of\n Directed Steiner Tree<\/jats:sc>\n in planar graphs where\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of terminals. We extend our approach to\n Multi-Rooted Directed Steiner Tree<\/jats:sc>\n , in which we get a\n \n \\(O(R+\\log k)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation for planar graphs for which\n \n \\( R \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of roots.\n <\/jats:p>","DOI":"10.1145\/3734525","type":"journal-article","created":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T12:02:31Z","timestamp":1746619351000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A \\(\\boldsymbol{O}(\\textbf{log}\\,\\boldsymbol{k})\\) -Approximation for\n Directed Steiner Tree<\/scp>\n in Planar Graphs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4039-3235","authenticated-orcid":false,"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[{"name":"Computing Science, University of Alberta, Edmonton, Alberta, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6843-6044","authenticated-orcid":false,"given":"Ramin","family":"Mousavi","sequence":"additional","affiliation":[{"name":"Computing Science, University of Alberta, Edmonton, Alberta, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","unstructured":"Marshall Bern and Paul Plassmann. 1989. The Steiner problem with edge lengths 1 and 2. Information Processing Letters 32 4 (1989) 171\u2013176.","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-005-1412-9"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2024.42"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520049"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601070"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.13"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1181"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Bundit Laekhanukit and Shi Li. 2022. \\(O(\\log^{2}k\/\\log\\log k)\\) -approximation algorithm for directed Steiner tree: A tight quasi-polynomial time algorithm. SIAM Journal on Computing 52 2 (2022) STOC19-298\u2013STOC19-322.","DOI":"10.1137\/20M1312988"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","unstructured":"Richard J. Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36 2 (1979) 177\u2013189.","DOI":"10.1137\/0136016"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1086"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523690"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3734525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:38Z","timestamp":1757346698000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3734525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3734525"],"URL":"https:\/\/doi.org\/10.1145\/3734525","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2024-02-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}