{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T09:16:04Z","timestamp":1754558164761,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Austrian Science Fund","award":["P 31119"],"award-info":[{"award-number":["P 31119"]}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2016116","2018302"],"award-info":[{"award-number":["2016116","2018302"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s00453-022-01020-z","type":"journal-article","created":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T06:08:51Z","timestamp":1659679731000},"page":"133-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Study of Steiner Tree on Unit Disk Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0154-5013","authenticated-orcid":false,"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2975-4856","authenticated-orcid":false,"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3636-5322","authenticated-orcid":false,"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,5]]},"reference":[{"key":"1020_CR1","doi-asserted-by":"crossref","unstructured":"Karp, R.\u00a0M.: Reducibility among combinatorial problems. In Miller, R.\u00a0E., Thatcher, J.\u00a0W., Bohlinger, J.\u00a0D. editors, Complexity of Computer Computations, pages 85\u2013103, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1020_CR2","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer Science & Business Media, (2013)"},{"issue":"4","key":"1020_CR3","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"Michael R Garey","year":"1977","unstructured":"Garey, Michael R., Johnson, David S.: The rectilinear steiner tree problem is np-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"5","key":"1020_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"Sanjeev Arora","year":"1998","unstructured":"Arora, Sanjeev: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM) 45(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"1020_CR5","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"Piotr Berman","year":"1994","unstructured":"Berman, Piotr, Ramaiyer, Viswanathan: Improved approximations for the steiner tree problem. J. Algorithms 17(3), 381\u2013408 (1994)","journal-title":"J. Algorithms"},{"issue":"3","key":"1020_CR6","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"Al Borchers","year":"1997","unstructured":"Borchers, Al., Ding-Zhu, Du.: Thek-steiner ratio in graphs. SIAM J. Comput. 26(3), 857\u2013869 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1020_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"Marek Karpinski","year":"1997","unstructured":"Karpinski, Marek, Zelikovsky, Alexander: New approximation algorithms for the steiner tree problems. J. Comb. Optim. 1(1), 47\u201365 (1997)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"1020_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"HJ Pr\u00f6mel","year":"2000","unstructured":"Pr\u00f6mel, H.J., Steger, A.: A new approximation algorithm for the steiner tree problem with performance ratio 5\/3. J. Algorithms 36(1), 89\u2013101 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"1020_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"Janka Chlebikova","year":"2008","unstructured":"Chlebikova, Janka, Chleb\u00edk, M.: The steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"1020_CR10","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M., Zelikovsky, A.: 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. In Workshop on Algorithms and Data Structures, pages 86\u201397. Springer, (2009)","DOI":"10.1007\/978-3-642-03367-4_8"},{"issue":"3","key":"1020_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"Stuart E Dreyfus","year":"1971","unstructured":"Dreyfus, Stuart E., Wagner, Robert A.: The steiner problem in graphs. Networks 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"issue":"3","key":"1020_CR12","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"Bernhard Fuchs","year":"2007","unstructured":"Fuchs, Bernhard, Kern, Walter, M\u00f6lle, Daniel, Richter, Stefan, Rossmanith, Peter, Wang, Xinhui: Dynamic programming for minimum Steiner trees. Theory of Comput. Syst. 41(3), 493\u2013500 (2007)","journal-title":"Theory of Comput. Syst."},{"issue":"4","key":"1020_CR13","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"Jesper Nederlof","year":"2013","unstructured":"Nederlof, Jesper: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868\u2013884 (2013)","journal-title":"Algorithmica"},{"key":"1020_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer Science & Business Media, (2012)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"1020_CR15","doi-asserted-by":"crossref","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., nd\u0159ej Such\u1ef3, O.: Parameterized complexity of directed steiner tree on sparse graphs. In European Symposium on Algorithms, pages 671\u2013682. Springer, (2013)","DOI":"10.1007\/978-3-642-40450-4_57"},{"issue":"1","key":"1020_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00453-016-0249-1","volume":"79","author":"Ond\u0159ej Such\u1ef3","year":"2017","unstructured":"Such\u1ef3, Ond\u0159ej: Extending the kernel for planar steiner tree to the number of steiner vertices. Algorithmica 79(1), 189\u2013210 (2017)","journal-title":"Algorithmica"},{"key":"1020_CR17","unstructured":"Dvo\u0159\u00e1k, P., Emil Feldmann, A., Knop, D., Masa\u0159\u00edk, T., Toufar, T., Vesel\u1ef3, P.: Parameterized approximation schemes for steiner trees with small number of steiner vertices. arXiv preprint arXiv:1710.00668, (2017)"},{"issue":"6","key":"1020_CR18","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"DW Wang","year":"1988","unstructured":"Wang, D.W., Kuo, Y.-S.: A study on two geometric location problems. Inf. Process. Lett. 28(6), 281\u2013286 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"1020_CR19","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"William K Hale","year":"1980","unstructured":"Hale, William K.: Frequency assignment: Theory and applications. Proc. IEEE 68(12), 1497\u20131514 (1980)","journal-title":"Proc. IEEE"},{"issue":"4","key":"1020_CR20","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1109\/JSAC.1984.1146097","volume":"2","author":"Karl Kammerlander","year":"1984","unstructured":"Kammerlander, Karl: C 900-an advanced mobile radio telephone system with optimum frequency utilization. IEEE J. Sel. Areas Commun. 2(4), 589\u2013597 (1984)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"1020_CR21","doi-asserted-by":"crossref","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. In Annals of Discrete Mathematics, volume\u00a048, pages 165\u2013177. Elsevier, (1991)","DOI":"10.1016\/S0167-5060(08)71047-1"},{"key":"1020_CR22","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs. In Graphs and Combinatorics, volume\u00a027, pages 399\u2013411. Springer, (2011)","DOI":"10.1007\/s00373-011-1026-1"},{"key":"1020_CR23","doi-asserted-by":"crossref","unstructured":"Li, X, Xu, X-H., Zou, F., Du, H., Wan, P., Wang, Y., Wu, W.: A ptas for node-weighted steiner tree in unit disk graphs. In International Conference on Combinatorial Optimization and Applications, pages 36\u201348. Springer, (2009)","DOI":"10.1007\/978-3-642-02026-1_4"},{"issue":"6","key":"1020_CR24","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.comgeo.2015.02.004","volume":"48","author":"Ahmad Biniaz","year":"2015","unstructured":"Biniaz, Ahmad, Maheshwari, Anil, Smid, Michiel: On full steiner trees in unit disk graphs. Comput. Geom. 48(6), 453\u2013458 (2015)","journal-title":"Comput. Geom."},{"key":"1020_CR25","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M., Pilipczuk, M.: On subexponential parameterized algorithms for steiner tree and directed subset tsp on planar graphs. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 474\u2013484. IEEE, (2018)","DOI":"10.1109\/FOCS.2018.00052"},{"key":"1020_CR26","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Marx, D., van\u00a0der Zanden, T.C.: A framework for eth-tight algorithms and lower bounds in geometric intersection graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 574\u2013586, (2018)","DOI":"10.1145\/3188745.3188854"},{"issue":"4","key":"1020_CR27","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s00454-018-00054-x","volume":"62","author":"Fedor V Fomin","year":"2019","unstructured":"Fomin, Fedor V., Lokshtanov, Daniel, Panolan, Fahad, Saurabh, Saket, Zehavi, Meirav: Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discret. Comput. Geometry 62(4), 879\u2013911 (2019)","journal-title":"Discret. Comput. Geometry"},{"key":"1020_CR28","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M, Pilipczuk, M., Saurabh, S.: Parameterized algorithms, volume\u00a04. Springer, (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"1","key":"1020_CR29","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-013-9788-x","volume":"71","author":"A Karim Abu-Affash","year":"2015","unstructured":"Karim Abu-Affash, A.: The euclidean bottleneck full steiner tree problem. Algorithmica 71(1), 139\u2013151 (2015)","journal-title":"Algorithmica"},{"key":"1020_CR30","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pages 138\u2013148, (1990)"},{"key":"1020_CR31","doi-asserted-by":"crossref","unstructured":"Bodlaender. H.L.: A linear time algorithm for finding tree-decompositions of small treewidth, (1996)","DOI":"10.1137\/S0097539793251219"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01020-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01020-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01020-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T12:06:43Z","timestamp":1674043603000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01020-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,5]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1020"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01020-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,8,5]]},"assertion":[{"value":"6 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}