{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T23:49:37Z","timestamp":1742946577813,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030420703"},{"type":"electronic","value":"9783030420710"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-42071-0_5","type":"book-chapter","created":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T17:02:44Z","timestamp":1587574964000},"page":"31-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs"],"prefix":"10.1007","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[]},{"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for Euclidean TSP. In: Proceedings of the 59th IEEE Symposium Foundations Computer Science (FOCS), pp. 450\u2013461 (2018)","DOI":"10.1109\/FOCS.2018.00050"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Marx, D., van der Zanden, T.C.: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. In: Proceedings of the 50th ACM Symposium Theory Computer (STOC), pp. 574\u2013586 (2018)","DOI":"10.1145\/3188745.3188854"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2018.10.007","volume":"769","author":"M de Berg","year":"2019","unstructured":"de Berg, M., Kisfaludi-Bak, S., Woeginger, G.: The complexity of dominating set in geometric intersection graphs. Theor. Comput. Sci. 769, 18\u201331 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"5_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."},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^k n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR6","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-006-1226-x","volume":"47","author":"F van den Eijkhof","year":"2007","unstructured":"van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica 47(2), 139\u2013158 (2007)","journal-title":"Algorithmica"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9, 3\u201324 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"5_CR8","unstructured":"Bringmann, K., Kisfaludi-Bak, S., Pilipczuk, M., van Leeuwen, E.J.: On geometric set cover for orthants. In: Proceedings of the 27th European Symposium on Algorithms (ESA), pp. 26:1\u201326:18 (2019)"},{"key":"5_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"2","key":"5_CR10","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 k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"RJ Kang","year":"2012","unstructured":"Kang, R.J., M\u00fcller, T.: Sphere and dot product representations of graphs. Discret. Comput. Geom. 47, 548\u2013568 (2012)","journal-title":"Discret. Comput. Geom."},{"key":"5_CR12","unstructured":"Kisfaludi-Bak, S.: ETH-tight algorithms for geometric network problems. Ph.D. thesis, Technische Universiteit Eidnhoven (2019)"},{"key":"5_CR13","unstructured":"Kisfaludi-Bak, S., Marx, D., van der Zanden, T.C.: How does object fatness impact the complexity of packing in d dimensions? In: Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC) (2019, to appear)"},{"key":"5_CR14","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung (1936). Hirzel"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. App. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. App. Math."},{"issue":"3","key":"5_CR16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D.: The square root phenomenon in planar graphs. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), part II, p. 28 (2013)","DOI":"10.1007\/978-3-642-39212-2_4"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1007\/978-3-662-48350-3_72","volume-title":"Algorithms - ESA 2015","author":"D Marx","year":"2015","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 865\u2013877. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72"}],"container-title":["Lecture Notes in Computer Science","Treewidth, Kernels, and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-42071-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,18]],"date-time":"2022-12-18T14:03:06Z","timestamp":1671372186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-42071-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030420703","9783030420710"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-42071-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}