{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:29:27Z","timestamp":1743092967699,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031555978"},{"type":"electronic","value":"9783031555985"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-55598-5_19","type":"book-chapter","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T18:01:53Z","timestamp":1709661713000},"page":"288-302","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Guarding Polyominoes Under k-Hop Visibility"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3978-1428","authenticated-orcid":false,"given":"Omrit","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5832-8135","authenticated-orcid":false,"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1342-8618","authenticated-orcid":false,"given":"Bengt J.","family":"Nilsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0846-5163","authenticated-orcid":false,"given":"Christian","family":"Rieck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2548-5756","authenticated-orcid":false,"given":"Christiane","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM 69(1), 4:1\u20134:70 (2022). https:\/\/doi.org\/10.1145\/3486220","key":"19_CR1","DOI":"10.1145\/3486220"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.dam.2022.06.006","volume":"320","author":"AK Abu-Affash","year":"2022","unstructured":"Abu-Affash, A.K., Carmi, P., Krasin, A.: A linear-time algorithm for minimum k-hop dominating set of a cactus graph. Discret. Appl. Math. 320, 488\u2013499 (2022). https:\/\/doi.org\/10.1016\/j.dam.2022.06.006","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"publisher","unstructured":"Amis, A.D., Prakash, R., Huynh, D.T., Vuong, T.H.: Max-Min $$d$$-cluster formation in wireless ad hoc networks. In: Conference on Computer Communications, pp. 32\u201341 (2000). https:\/\/doi.org\/10.1109\/INFCOM.2000.832171","key":"19_CR3","DOI":"10.1109\/INFCOM.2000.832171"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"101687","DOI":"10.1016\/j.comgeo.2020.101687","volume":"92","author":"B Aronov","year":"2021","unstructured":"Aronov, B., Donakonda, A., Ezra, E., Pinchasi, R.: On pseudo-disk hypergraphs. Comput. Geom. 92, 101687 (2021). https:\/\/doi.org\/10.1016\/j.comgeo.2020.101687","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Basuchowdhuri, P., Majumder, S.: Finding influential nodes in social networks using minimum $$k$$-hop dominating set. In: International Conference on Applied Algorithms (ICAA), pp. 137\u2013151 (2014). https:\/\/doi.org\/10.1007\/978-3-319-04126-1_12","key":"19_CR5","DOI":"10.1007\/978-3-319-04126-1_12"},{"issue":"03","key":"19_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(03), 187\u2013205 (2012). https:\/\/doi.org\/10.1142\/S0218195912500045","journal-title":"Int. J. Comput. Geom. Appl."},{"doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding polyominoes. In: Symposium on Computational Geometry (SoCG), pp. 387\u2013396 (2011). https:\/\/doi.org\/10.1145\/1998196.1998261","key":"19_CR7","DOI":"10.1145\/1998196.1998261"},{"doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Mehrabi, S.: On $$r$$-guarding thin orthogonal polygons. In: International Symposium on Algorithms and Computation (ISAAC), pp. 17:1\u201317:13 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.17","key":"19_CR8","DOI":"10.4230\/LIPIcs.ISAAC.2016.17"},{"issue":"2","key":"19_CR9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00453-020-00769-5","volume":"83","author":"TC Biedl","year":"2021","unstructured":"Biedl, T.C., Mehrabi, S.: On orthogonally guarding orthogonal polygons with bounded treewidth. Algorithmica 83(2), 641\u2013666 (2021). https:\/\/doi.org\/10.1007\/s00453-020-00769-5","journal-title":"Algorithmica"},{"doi-asserted-by":"publisher","unstructured":"Borradaile, G., Le, H.: Optimal dynamic program for $$r$$-domination problems over tree decompositions. In: International Symposium on Parameterized and Exact Computation (IPEC), pp. 8:1\u20138:23 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.8","key":"19_CR10","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"issue":"4","key":"19_CR11","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995). https:\/\/doi.org\/10.1007\/BF02570718","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for $$(k, r)$$-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005). https:\/\/doi.org\/10.1145\/1077464.1077468","journal-title":"ACM Trans. Algorithms"},{"doi-asserted-by":"publisher","unstructured":"Filtser, A., Le, H.: Clan embeddings into trees, and low treewidth graphs. In: Symposium on Theory of Computing (STOC), pp. 342\u2013355 (2021). https:\/\/doi.org\/10.1145\/3406325.3451043","key":"19_CR13","DOI":"10.1145\/3406325.3451043"},{"doi-asserted-by":"publisher","unstructured":"Filtser, A., Le, H.: Low treewidth embeddings of planar and minor-free metrics. In: Symposium on Foundations of Computer Science (FOCS), pp. 1081\u20131092 (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00105","key":"19_CR14","DOI":"10.1109\/FOCS54457.2022.00105"},{"unstructured":"Filtser, O., Krohn, E., Nilsson, B.J., Rieck, C., Schmidt, C.: Guarding polyominoes under $$k$$-hop visibility (2023). https:\/\/arxiv.org\/abs\/2308.00334","key":"19_CR15"},{"doi-asserted-by":"publisher","unstructured":"Fox-Epstein, E., Klein, P.N., Schild, A.: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. In: Symposium on Discrete Algorithms (SODA), pp. 1069\u20131088 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.66","key":"19_CR16","DOI":"10.1137\/1.9781611975482.66"},{"doi-asserted-by":"publisher","unstructured":"Gibson, M., Krohn, E., Wang, Q.: The VC-dimension of visibility on the boundary of a simple polygon. In: International Symposium on Algorithms and Computation (ISAAC), pp. 541\u2013551 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_46","key":"19_CR17","DOI":"10.1007\/978-3-662-48971-0_46"},{"issue":"1","key":"19_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2013.08.012","volume":"47","author":"A Gilbers","year":"2014","unstructured":"Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61\u201374 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2013.08.012","journal-title":"Comput. Geom."},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete Comput. Geom. 2(2), 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/BF02187876","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Iwamoto, C., Kume, T.: Computational complexity of the $$r$$-visibility guard set problem for polyominoes. In: Japanese Conference on Discrete and Computational Geometry and Graphs (JCDCGG), pp. 87\u201395 (2013). https:\/\/doi.org\/10.1007\/978-3-319-13287-7_8","key":"19_CR20","DOI":"10.1007\/978-3-319-13287-7_8"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.dam.2018.11.002","volume":"264","author":"I Katsikarelis","year":"2019","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for $$(k, r)$$-center. Discret. Appl. Math. 264, 90\u2013117 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.11.002","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"19_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.ipl.2015.07.014","volume":"116","author":"S Kundu","year":"2016","unstructured":"Kundu, S., Majumder, S.: A linear time algorithm for optimal k-hop dominating set of a tree. Inf. Process. Lett. 116(2), 197\u2013202 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.07.014","journal-title":"Inf. Process. Lett."},{"unstructured":"Langetepe, E., Lehmann, S.: Exact VC-dimension for $${L}_1$$-visibility of points in simple polygons (2017). https:\/\/arxiv.org\/abs\/1705.01723","key":"19_CR23"},{"issue":"2","key":"19_CR24","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D Lee","year":"1986","unstructured":"Lee, D., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986). https:\/\/doi.org\/10.1109\/TIT.1986.1057165","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"19_CR25","doi-asserted-by":"publisher","first-page":"225","DOI":"10.2140\/pjm.1975.61.225","volume":"61","author":"A Meir","year":"1975","unstructured":"Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pac. J. Math. 61(1), 225\u2013233 (1975). https:\/\/doi.org\/10.2140\/pjm.1975.61.225","journal-title":"Pac. J. Math."},{"issue":"2","key":"19_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J., Supowit, K.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181\u2013190 (1983). https:\/\/doi.org\/10.1109\/TIT.1983.1056648","journal-title":"IEEE Trans. Inf. Theory"},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.endm.2015.06.024","volume":"49","author":"V Pinciu","year":"2015","unstructured":"Pinciu, V.: Guarding polyominoes, polycubes and polyhypercubes. Electron. Notes Discrete Math. 49, 159\u2013166 (2015). https:\/\/doi.org\/10.1016\/j.endm.2015.06.024","journal-title":"Electron. Notes Discrete Math."},{"doi-asserted-by":"publisher","unstructured":"Tom\u00e1s, A.P.: Guarding thin orthogonal polygons is hard. In: Gasieniec, L., Wolter, F. (eds.) FCT 2013. LNCS, vol. 8070, pp. 305\u2013316. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40164-0_29","key":"19_CR28","DOI":"10.1007\/978-3-642-40164-0_29"},{"issue":"1","key":"19_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02897056","volume":"104","author":"P Valtr","year":"1998","unstructured":"Valtr, P.: Guarding galleries where no point sees a small area. Israel J. Math. 104(1), 1\u201316 (1998). https:\/\/doi.org\/10.1007\/BF02897056","journal-title":"Israel J. Math."},{"issue":"2","key":"19_CR30","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"C Worman","year":"2007","unstructured":"Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Appl. 17(2), 105\u2013138 (2007). https:\/\/doi.org\/10.1142\/S0218195907002264","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Lecture Notes in Computer Science","LATIN 2024: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-55598-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T18:03:33Z","timestamp":1709661813000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-55598-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031555978","9783031555985"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-55598-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Varas","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/latin2024.cmm.uchile.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}