{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:16Z","timestamp":1740109276285,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00453-019-00567-8","type":"journal-article","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T16:28:38Z","timestamp":1554481718000},"page":"2934-2962","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms"],"prefix":"10.1007","volume":"81","author":[{"given":"Mark de","family":"Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-2902","authenticated-orcid":false,"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"567_CR1","doi-asserted-by":"publisher","unstructured":"Alzoubi, K.M., Wan, P., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2002, 9\u201311 June 2002, Lausanne, Switzerland, pp. 157\u2013164. ACM (2002). \n                    https:\/\/doi.org\/10.1145\/513800.513820","DOI":"10.1145\/513800.513820"},{"key":"567_CR2","doi-asserted-by":"publisher","unstructured":"Amb\u00fchl, C.: An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In: ICALP, Proceedings, pp. 1139\u20131150 (2005). \n                    https:\/\/doi.org\/10.1007\/11523468_92","DOI":"10.1007\/11523468_92"},{"key":"567_CR3","doi-asserted-by":"publisher","unstructured":"Amb\u00fchl, C., Clementi, A.E.F., Ianni, M.D., Lev-Tov, N., Monti, A., Peleg, D., Rossi, G., Silvestri, R.: Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks. In: STACS, Proceedings, pp. 418\u2013427 (2004). \n                    https:\/\/doi.org\/10.1007\/978-3-540-24749-4_37","DOI":"10.1007\/978-3-540-24749-4_37"},{"key":"567_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"567_CR5","unstructured":"Breu, H.: Algorithmic aspects of constrained unit disk graphs. Ph.D. thesis, University of British Columbia (1996)"},{"issue":"4","key":"567_CR6","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.comgeo.2014.12.003","volume":"48","author":"S Cabello","year":"2015","unstructured":"Cabello, S., Jej\u010di\u010d, M.: Shortest paths in intersection graphs of unit disks. Comput. Geom. 48(4), 360\u2013367 (2015). \n                    https:\/\/doi.org\/10.1016\/j.comgeo.2014.12.003","journal-title":"Comput. Geom."},{"issue":"1","key":"567_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A data structuring technique. Algorithmica 1(1), 133\u2013162 (1986)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"567_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1\u20133), 165\u2013177 (1990). \n                    https:\/\/doi.org\/10.1016\/0012-365X(90)90358-O","journal-title":"Discrete Math."},{"key":"567_CR9","doi-asserted-by":"crossref","unstructured":"Clementi, A.E., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: A worst-case analysis of an MST-based heuristic to construct energy-efficient broadcast trees in wireless networks. In: STACS, Proceedings, pp. 121\u2013131 (2001)","DOI":"10.1007\/3-540-44693-1_11"},{"issue":"1\u20133","key":"567_CR10","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2005.11.046","volume":"352","author":"GK Das","year":"2006","unstructured":"Das, G.K., Das, S., Nandy, S.C.: Range assignment for energy efficient broadcasting in linear radio networks. Theor. Comput. Sci. 352(1\u20133), 332\u2013341 (2006). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2005.11.046","journal-title":"Theor. Comput. Sci."},{"key":"567_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00561-0","author":"M Berg de","year":"2017","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S.: The homogeneous broadcast problem in narrow and wide strips II: lower bounds. Algorithmica (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-019-00561-0","journal-title":"Algorithmica"},{"key":"567_CR12","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for Euclidean TSP. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7\u20139 October 2018, pp. 450\u2013461. IEEE Computer Society (2018). \n                    https:\/\/doi.org\/10.1109\/FOCS.2018.00050\n                    \n                  . Preprint \n                    arxiv:1807.06933","DOI":"10.1109\/FOCS.2018.00050"},{"key":"567_CR13","doi-asserted-by":"publisher","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 STOC 2018, pp. 574\u2013586. ACM (2018). \n                    https:\/\/doi.org\/10.1145\/3188745.3188854","DOI":"10.1145\/3188745.3188854"},{"key":"567_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"567_CR15","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Kisfaludi-Bak, S., Woeginger, G.: The complexity of dominating set in geometric intersection graphs. Theor. Comput. Sci. (2018). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2018.10.007","DOI":"10.1016\/j.tcs.2018.10.007"},{"issue":"3","key":"567_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.orl.2005.04.013","volume":"34","author":"VG Deineko","year":"2006","unstructured":"Deineko, V.G., Klinz, B., Woeginger, G.J.: Exact algorithms for the Hamiltonian cycle problem in planar graphs. Oper. Res. Lett. 34(3), 269\u2013274 (2006). \n                    https:\/\/doi.org\/10.1016\/j.orl.2005.04.013","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"567_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195\u2013207 (1971). \n                    https:\/\/doi.org\/10.1002\/net.3230010302","journal-title":"Networks"},{"issue":"2","key":"567_CR18","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"567_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006). \n                    https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"issue":"4","key":"567_CR20","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/net.20227","volume":"52","author":"B Fuchs","year":"2008","unstructured":"Fuchs, B.: On the hardness of range assignment problems. Networks 52(4), 183\u2013195 (2008). \n                    https:\/\/doi.org\/10.1002\/net.20227","journal-title":"Networks"},{"key":"567_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"567_CR22","doi-asserted-by":"publisher","unstructured":"Hartenstein, H., Bochow, B., Ebner, A., Lott, M., Radimirsch, M., Vollmer, D.: Position-aware ad hoc wireless networks for inter-vehicle communications: the fleetnet project. In: Proceedings of the 2nd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2001, 4\u20135 October 2001, Long Beach, CA, USA, pp. 259\u2013262. ACM (2001). \n                    https:\/\/doi.org\/10.1145\/501416.501454","DOI":"10.1145\/501416.501454"},{"issue":"1","key":"567_CR23","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985). \n                    https:\/\/doi.org\/10.1145\/2455.214106","journal-title":"J. ACM"},{"key":"567_CR24","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Borowsky, E., Rajsbaum, S. (eds.) Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, 13\u201316 July 2003, pp. 63\u201372. ACM (2003). \n                    https:\/\/doi.org\/10.1145\/872035.872044","DOI":"10.1145\/872035.872044"},{"issue":"2","key":"567_CR25","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982). \n                    https:\/\/doi.org\/10.1137\/0211025","journal-title":"SIAM J. Comput."},{"key":"567_CR26","doi-asserted-by":"publisher","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, Second International Workshop, IWPEC, Proceedings, pp. 154\u2013165 (2006). \n                    https:\/\/doi.org\/10.1007\/11847250_14","DOI":"10.1007\/11847250_14"},{"key":"567_CR27","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: ESA, Proceedings, pp. 865\u2013877 (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72","DOI":"10.1007\/978-3-662-48350-3_72"},{"issue":"2","key":"567_CR28","first-page":"57","volume":"64","author":"S Masuyama","year":"1981","unstructured":"Masuyama, S., Ibaraki, T., Hasegawa, T.: The computational complexity of the \n                    \n                      \n                    \n                    $$m$$\n                    \n                      \n                        m\n                      \n                    \n                  -center problems on the plane. IEICE Trans. 64(2), 57\u201364 (1981)","journal-title":"IEICE Trans."},{"key":"567_CR29","doi-asserted-by":"crossref","unstructured":"Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: JCDCG, Proceedings, pp. 194\u2013200. Springer (1998)","DOI":"10.1007\/978-3-540-46515-7_16"},{"key":"567_CR30","unstructured":"van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects. Ph.D. thesis, Universiteit van Amsterdam (2009)"},{"issue":"2","key":"567_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.comcom.2012.10.005","volume":"36","author":"J Yu","year":"2013","unstructured":"Yu, J., Wang, N., Wang, G., Yu, D.: Connected dominating sets in wireless ad hoc and sensor networks\u2014a comprehensive survey. Comput. Commun. 36(2), 121\u2013134 (2013). \n                    https:\/\/doi.org\/10.1016\/j.comcom.2012.10.005","journal-title":"Comput. Commun."},{"key":"567_CR32","doi-asserted-by":"publisher","unstructured":"Zhang, L., Gao, J.: Load balanced short path routing in wireless networks. In: Proceedings IEEE INFOCOM 2004, The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1098\u20131107. IEEE (2004). \n                    https:\/\/doi.org\/10.1109\/INFCOM.2004.1356996","DOI":"10.1109\/INFCOM.2004.1356996"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00567-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00567-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00567-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T23:09:20Z","timestamp":1585955360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00567-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["567"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00567-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"12 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}