{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:42:29Z","timestamp":1775054549789,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T00:00:00Z","timestamp":1575936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740858, CCF-1712119, DMS-1839274"],"award-info":[{"award-number":["CCF-1740858, CCF-1712119, DMS-1839274"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            In the classical Steiner tree problem, given an undirected, connected graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with non-negative edge costs and a set of\n            <jats:italic>terminals<\/jats:italic>\n            <jats:italic>T<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            , the objective is to find a minimum-cost tree\n            <jats:italic>E<\/jats:italic>\n            <jats:sup>&amp;prime<\/jats:sup>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            that spans the terminals. The problem is APX-hard; the best-known approximation algorithm has a ratio of \u03c1 = ln (4)+\u03b5 &lt; 1.39. In this article, we study a natural generalization, the\n            <jats:italic>multi-level Steiner tree<\/jats:italic>\n            (MLST) problem: Given a nested sequence of terminals\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\u2113<\/jats:sub>\n            \u2282 \u2026 \u2282\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            , compute nested trees\n            <jats:italic>E<\/jats:italic>\n            <jats:sub>\u2113<\/jats:sub>\n            \u2286 \u2026 \u2286\n            <jats:italic>E<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            that span the corresponding terminal sets with minimum total cost.\n          <\/jats:p>\n          <jats:p>\n            The MLST problem and variants thereof have been studied under various names, including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-tier tree. Several approximation results are known. We first present two simple\n            <jats:italic>O<\/jats:italic>\n            (\u2113)-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most 2\u2113 Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present several integer linear programming formulations for the MLST problem and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to \u2113 = 100 levels, which is sufficient for most applications, such as network visualization or designing multi-level infrastructure.\n          <\/jats:p>","DOI":"10.1145\/3368621","type":"journal-article","created":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T13:21:36Z","timestamp":1575984096000},"page":"1-22","source":"Crossref","is-referenced-by-count":6,"title":["Multi-level Steiner Trees"],"prefix":"10.1145","volume":"24","author":[{"given":"Reyan","family":"Ahmed","sequence":"first","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Patrizio","family":"Angelini","sequence":"additional","affiliation":[{"name":"Universit\u00e4t T\u00fcbingen, Germany"}]},{"given":"Faryad Darabi","family":"Sahneh","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Alon","family":"Efrat","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"David","family":"Glickenstein","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Martin","family":"Gronemann","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu K\u00f6ln, Germany"}]},{"given":"Niklas","family":"Heinsohn","sequence":"additional","affiliation":[{"name":"Universit\u00e4t T\u00fcbingen, Germany"}]},{"given":"Stephen G.","family":"Kobourov","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Richard","family":"Spence","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Joseph","family":"Watkins","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[{"name":"Universit\u00e4t W\u00fcrzburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192726.3192730"},{"key":"e_1_2_1_3_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. Science 286, 5439 ( 1999 ), 509--512. DOI:https:\/\/doi.org\/10.1126\/science.286.5439.509 10.1126\/science.286.5439.509 Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512. DOI:https:\/\/doi.org\/10.1126\/science.286.5439.509"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3206505.3206531"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.826288"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361200"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u00f6s Paul","year":"1959","unstructured":"Paul Erd\u00f6s and Alfr\u00e9d R\u00e9nyi . 1959 . On random graphs I . Publicationes Mathematicae (Debrecen) 6 (1959), 290 -- 297 . Paul Erd\u00f6s and Alfr\u00e9d R\u00e9nyi. 1959. On random graphs I. Publicationes Mathematicae (Debrecen) 6 (1959), 290--297.","journal-title":"Publicationes Mathematicae (Debrecen)"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_12_1","unstructured":"Mathias Hauptmann and Marek Karpinski (eds.). 2015. A Compendium on Steiner Tree Problems. Retrieved from http:\/\/theory.cs.uni-bonn.de\/info5\/steinerkompendium\/.  Mathias Hauptmann and Marek Karpinski (eds.). 2015. A Compendium on Steiner Tree Problems. Retrieved from http:\/\/theory.cs.uni-bonn.de\/info5\/steinerkompendium\/."},{"key":"e_1_2_1_13_1","volume-title":"Complexity of Computer Computations, Raymond E","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among Combinatorial Problems . In Complexity of Computer Computations, Raymond E . Miller, James W. Thatcher, and Jean D. Bohlinger (Eds.). Plenum Press , New York , 85--103. DOI:https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9 10.1007\/978-1-4684-2001-2_9 Richard M. Karp. 1972. Reducibility among Combinatorial Problems. In Complexity of Computer Computations, Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger (Eds.). Plenum Press, New York, 85--103. DOI:https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1133-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.202"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00318-8"},{"key":"e_1_2_1_19_1","volume-title":"The Steiner Tree Problem","author":"Pr\u00f6mel Hans J\u00fcrgen","unstructured":"Hans J\u00fcrgen Pr\u00f6mel and Angelika Steger . 2002. The Steiner Tree Problem . Vieweg and Teubner Verlag , Wiesbaden . DOI:https:\/\/doi.org\/10.1007\/978-3-322-80291-0 10.1007\/978-3-322-80291-0 Hans J\u00fcrgen Pr\u00f6mel and Angelika Steger. 2002. The Steiner Tree Problem. Vieweg and Teubner Verlag, Wiesbaden. DOI:https:\/\/doi.org\/10.1007\/978-3-322-80291-0"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_21_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H . Strogatz . 1998 . Collective dynamics of \u2019small-world\u2019 networks. Nature 393, 6684 (1998), 440--442. DOI:https:\/\/doi.org\/10.1038\/30918 10.1038\/30918 Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2019small-world\u2019 networks. Nature 393, 6684 (1998), 440--442. DOI:https:\/\/doi.org\/10.1038\/30918"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/34233.34235"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0050-6"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368621","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:42Z","timestamp":1750202622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,10]]},"references-count":23,"alternative-id":["10.1145\/3368621"],"URL":"https:\/\/doi.org\/10.1145\/3368621","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,10]]}}}