{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:05Z","timestamp":1740109325623,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"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"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00453-021-00913-9","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T12:04:52Z","timestamp":1641470692000},"page":"961-981","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameter Analysis for Guarding Terrains"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"key":"913_CR1","unstructured":"Agrawal, A., Knudsen, K.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: The parameterized complexity of guarding almost convex polygons. In: 36th International Symposium on Computational Geometry (SoCG), vol. 164, pp. 3:1\u20133:16 (2020)"},{"key":"913_CR2","doi-asserted-by":"crossref","unstructured":"Ashok, P., Fomin, F.V., Kolay, S., Saurabh, S., Zehavi, M.: Exact algorithms for terrain guarding. ACM Trans. Algorithms 14(2), 25:1\u201325:20 (2018)","DOI":"10.1145\/3186897"},{"issue":"6","key":"913_CR3","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1137\/S0097539704446384","volume":"36","author":"B Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal 1.5d terrain guarding. SIAM J. Comput. 36(6), 1631\u20131647 (2007)","journal-title":"SIAM J. Comput."},{"key":"913_CR4","unstructured":"Bonnet, \u00c9., Giannopoulos, P.: Orthogonal terrain guarding is NP-complete. In: Symposium on Computational Geometry, SoCG 2018, pp. 11:1\u201311:15 (2018)"},{"issue":"2","key":"913_CR5","first-page":"21","volume":"10","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Giannopoulos, P.: Orthogonal terrain guarding is NP-complete. JoCG 10(2), 21\u201344 (2019)","journal-title":"JoCG"},{"issue":"4","key":"913_CR6","doi-asserted-by":"publisher","first-page":"42:1","DOI":"10.1145\/3398684","volume":"16","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. ACM Trans. Algorithms 16(4), 42:1-42:23 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"913_CR7","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proceedings of the 7th Canadian Conference on Computational Geometry, CCCG, pp. 133\u2013138 (1995)"},{"issue":"1","key":"913_CR8","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"913_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., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"913_CR10","volume-title":"Graph Theory, 4th Edition, volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, 4th Edition, volume 173 of Graduate Texts in Mathematics. Springer, Berlin (2012)"},{"key":"913_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"913_CR12","unstructured":"Durocher, S., Li, P.C., Mehrabi, S.: Guarding orthogonal terrains. In: Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG (2015)"},{"issue":"2","key":"913_CR13","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00453-009-9358-4","volume":"60","author":"MK Elbassioni","year":"2011","unstructured":"Elbassioni, M.K., Krohn, E., Matijevic, D., Mestre, J., Severdija, D.: Improved approximations for guarding 1.5-dimensional terrains. Algorithmica 60(2), 451\u2013463 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"913_CR14","first-page":"256","volume":"7","author":"S Friedrichs","year":"2016","unstructured":"Friedrichs, S., Hemmer, M., King, J., Schmidt, C.: The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS. JoCG 7(1), 256\u2013284 (2016)","journal-title":"JoCG"},{"key":"913_CR15","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)"},{"issue":"1","key":"913_CR16","first-page":"168","volume":"5","author":"M Gibson","year":"2014","unstructured":"Gibson, M., Kanade, G., Krohn, E., Varadarajan, K.: Guarding terrains via local search. JoCG 5(1), 168\u2013178 (2014)","journal-title":"JoCG"},{"issue":"3","key":"913_CR17","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2007.02.002","volume":"39","author":"MJ Katz","year":"2008","unstructured":"Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. 39(3), 219\u2013228 (2008)","journal-title":"Comput. Geom."},{"key":"913_CR18","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.tcs.2015.06.028","volume":"595","author":"F Khodakarami","year":"2015","unstructured":"Khodakarami, F., Didehvar, F., Mohades, A.: A fixed-parameter algorithm for guarding 1.5D terrains. Theor. Comput. Sci. 595, 130\u2013142 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"913_CR19","doi-asserted-by":"crossref","unstructured":"King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Proceedings of the 7th Latin American Symposium on Theoretical Informatics, LATIN, vol. 3887, pp. 629\u2013640 (2006)","DOI":"10.1007\/11682462_58"},{"issue":"5","key":"913_CR20","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1137\/100791506","volume":"40","author":"J King","year":"2011","unstructured":"King, J., Krohn, E.: Terrain guarding is np-hard. SIAM J. Comput. 40(5), 1316\u20131339 (2011)","journal-title":"SIAM J. Comput."},{"key":"913_CR21","unstructured":"Lyu, Y., \u00dcng\u00f6r, A.: A fast 2-approximation algorithm for guarding orthogonal terrains. In: Proceedings of the 28th Canadian Conference on Computational Geometry, CCCG, pp. 161\u2013167 (2016)"},{"key":"913_CR22","unstructured":"Mehrabi, S.: Guarding the vertices of an orthogonal terrain using vertex guards (2015). arXiv:1512.08292"},{"key":"913_CR23","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press Inc., Oxford (1987)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00913-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00913-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00913-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:09:00Z","timestamp":1647443340000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00913-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["913"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00913-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"13 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}