{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:11Z","timestamp":1781077511645,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T00:00:00Z","timestamp":1552953600000},"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-00561-0","type":"journal-article","created":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T12:28:11Z","timestamp":1555504091000},"page":"2963-2990","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds"],"prefix":"10.1007","volume":"81","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-2902","authenticated-orcid":false,"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,3,19]]},"reference":[{"key":"561_CR1","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S.: The homogeneous broadcast problem in narrow and wide strips I: algorithms. Algorithmica (submitted)"},{"key":"561_CR2","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, June 9\u201311, 2002, pp. 157\u2013164. ACM, Lausanne (2002). \n                    https:\/\/doi.org\/10.1145\/513800.513820","DOI":"10.1145\/513800.513820"},{"key":"561_CR3","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 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 13\u201316, 2003, pp. 63\u201372. ACM, New York (2003). \n                    https:\/\/doi.org\/10.1145\/872035.872044","DOI":"10.1145\/872035.872044"},{"issue":"2","key":"561_CR4","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":"561_CR5","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, San Francisco (1979)"},{"issue":"2","key":"561_CR6","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."},{"issue":"2","key":"561_CR7","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":"561_CR8","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, New York (2018). \n                    https:\/\/doi.org\/10.1145\/3188745.3188854","DOI":"10.1145\/3188745.3188854"},{"key":"561_CR9","doi-asserted-by":"publisher","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, 2nd International Workshop, IWPEC, Proceedings, pp. 154\u2013165 (2006). \n                    https:\/\/doi.org\/10.1007\/11847250_14","DOI":"10.1007\/11847250_14"},{"key":"561_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.10.007","author":"M Berg de","year":"2018","unstructured":"de Berg, 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","journal-title":"Theor. Comput. Sci."},{"key":"561_CR11","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":"2","key":"561_CR12","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). \n                    https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"561_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"561_CR14","doi-asserted-by":"publisher","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20\u201323, 2007, Providence, RI, USA, Proceedings, pp. 338\u2013348. IEEE Computer Society, New York (2007). \n                    https:\/\/doi.org\/10.1109\/FOCS.2007.50","DOI":"10.1109\/FOCS.2007.50"},{"key":"561_CR15","doi-asserted-by":"publisher","unstructured":"Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when \n                    \n                      \n                    \n                    $$1-1\/d$$\n                    \n                      \n                        \n                          1\n                          -\n                          1\n                          \/\n                          d\n                        \n                      \n                    \n                   is the best possible exponent for \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -dimensional geometric problems. In: Proceedings of the 30th Annual Symposium on Computational Geometry, SOCG 2014, pp. 67\u201376. ACM, New York (2014). \n                    https:\/\/doi.org\/10.1145\/2582112.2582124","DOI":"10.1145\/2582112.2582124"},{"key":"561_CR16","doi-asserted-by":"publisher","unstructured":"Bir\u00f3, C., Bonnet, \u00c9., Marx, D., Miltzow, T., Rz\u0105\u017cewski, P.: Fine-grained complexity of coloring unit disks and balls. In: Proceedings of SoCG 2017, pp. 18:1\u201318:16 (2017). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.18","DOI":"10.4230\/LIPIcs.SoCG.2017.18"},{"key":"561_CR17","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M., Pilipczuk, M.: On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7\u20139, 2018, pp. 474\u2013484. IEEE Computer Society, New York (2018). \n                    https:\/\/doi.org\/10.1109\/FOCS.2018.00052","DOI":"10.1109\/FOCS.2018.00052"},{"key":"561_CR18","unstructured":"Kisfaludi-Bak, S., Nederlof, J., van Leeuwen, E.J.: Nearly ETH-tight algorithms for planar Steiner tree with terminals on few faces (2019). \n                    arXiv:1811.06871"},{"key":"561_CR19","doi-asserted-by":"crossref","unstructured":"Burton, B., Cabello, S., Kratsch, S., Pettersson, W.: The parameterized complexity of finding a 2-sphere in a simplicial complex. CoRR \n                    arXiv:1802.07175\n                    \n                   (2018)","DOI":"10.1137\/18M1168704"},{"key":"561_CR20","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in H-free graphs. e-prints \n                    arXiv:1810.04620\n                    \n                   (2018)"},{"key":"561_CR21","doi-asserted-by":"publisher","unstructured":"Amis, A.D., Prakash, R., Huynh, D., Vuong, T.: Max\u2013min d-cluster formation in wireless ad hoc networks. In: Proceedings IEEE INFOCOM 2000, the Conference on Computer Communications, 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Reaching the Promised Land of Communications, Tel Aviv, Israel, March 26\u201330, 2000, pp. 32\u201341. IEEE, New York (2000). \n                    https:\/\/doi.org\/10.1109\/INFCOM.2000.832171","DOI":"10.1109\/INFCOM.2000.832171"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00561-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00561-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00561-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:19:55Z","timestamp":1584490795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00561-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,19]]},"references-count":21,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["561"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00561-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,19]]},"assertion":[{"value":"12 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}