{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:55Z","timestamp":1740123535733,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T00:00:00Z","timestamp":1595462400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T00:00:00Z","timestamp":1595462400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s11227-020-03379-8","type":"journal-article","created":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T09:03:53Z","timestamp":1595495033000},"page":"3077-3109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["NP-completeness of chromatic orthogonal art gallery problem"],"prefix":"10.1007","volume":"77","author":[{"given":"Hamid","family":"Hoorfar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3542-7763","authenticated-orcid":false,"given":"Alireza","family":"Bagheri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,23]]},"reference":[{"key":"3379_CR1","doi-asserted-by":"crossref","unstructured":"Biedl Th, Irfan MT, Iwerks J, Kim J, Mitchell JSB (2011) Guarding polyominoes. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pp 387\u2013396","DOI":"10.1145\/1998196.1998261"},{"issue":"3","key":"3379_CR2","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"T Biedl","year":"1998","unstructured":"Biedl T, Kant G (1998) A better heuristic for orthogonal graph drawings. Comput Geom 9(3):159\u2013180","journal-title":"Comput Geom"},{"key":"3379_CR3","unstructured":"Biedl T, Mehrabi S (2016) On $$ r $$-guarding thin orthogonal polygons. arXiv preprint arXiv:1604.07100"},{"issue":"5","key":"3379_CR4","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1016\/j.patcog.2010.11.010","volume":"44","author":"A Bottino","year":"2011","unstructured":"Bottino A, Laurentini A (2011) A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recognit 44(5):1048\u20131056","journal-title":"Pattern Recognit"},{"key":"3379_CR5","doi-asserted-by":"crossref","unstructured":"\u00c7a\u011f\u0131r\u0131c\u0131 O, Ghosh SK, Hlin\u011bn\u1ef3 P, Roy B (2019) On conflict-free chromatic guarding of simple polygons. In: International Conference on Combinatorial Optimization and Applications. Springer, Berlin, pp 601\u2013612","DOI":"10.1007\/978-3-030-36412-0_49"},{"key":"3379_CR6","unstructured":"\u00c7a\u011firici O, Hlin\u011bn\u1ef3 P, Roy B (2019) On colourability of polygon visibility graphs. arXiv preprint arXiv:1906.01904"},{"issue":"4","key":"3379_CR7","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1111\/j.1475-3995.2011.00804.x","volume":"18","author":"MC Couto","year":"2011","unstructured":"Couto MC, de Rezende PJ, de Souza CC (2011) An exact algorithm for minimizing vertex guards on art galleries. Int Trans Oper Res 18(4):425\u2013448","journal-title":"Int Trans Oper Res"},{"key":"3379_CR8","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg M, Khosravi A (2010) Optimal binary space partitions in the plane. In: International Computing and Combinatorics Conference. Springer, Berlin, pp 216\u2013225","DOI":"10.1007\/978-3-642-14031-0_25"},{"key":"3379_CR9","unstructured":"D\u00f6rre P (2004) Every planar graph is 4-colourable and 5-choosable a joint proof. Unpublished note, Fachhochschule S\u00fcdwestfalen, University of Applied Sciences"},{"key":"3379_CR10","doi-asserted-by":"crossref","unstructured":"Durocher S, Mehrabi S (2012) Computing partitions of rectilinear polygons with minimum stabbing number. In: International Computing and Combinatorics Conference. Springer, Berlin, pp 228\u2013239","DOI":"10.1007\/978-3-642-32241-9_20"},{"key":"3379_CR11","unstructured":"Erickson L, LaValle SM (2010) A chromatic art gallery problem. Technical report"},{"key":"3379_CR12","doi-asserted-by":"crossref","unstructured":"Erickson LH, LaValle SM (2011) How many landmark colors are needed to avoid confusion in a polygon? In: 2011 IEEE International Conference on Robotics and Automation. IEEE, pp 2302\u20132307","DOI":"10.1109\/ICRA.2011.5979838"},{"key":"3379_CR13","unstructured":"Erickson LH, LaValle SM (2012) An art gallery approach to ensuring that landmarks are distinguishable. In: Durrant-Whyte H, Abbeel P,  Roy N (eds) Robotics: science and systems, vol 7, MIT Press Journals,  pp 81\u201388. ISSN (Print) 2330-7668, ISSN (Electronic) 2330-765X. https:\/\/scholar.google.com\/scholar?hl=en&as_sdt=0%2C5&q=+Erickson+LH%2C+LaValle+SM+%282012%29+An+art+gallery+approach+to+ensuring+that+landmarks+are+distinguishable.+In%3A+Robotics%3A+science+and+systems%2C+vol+7%2C+pp+81%E2%80%9388&btn"},{"key":"3379_CR14","unstructured":"Fekete SP, Friedrichs S, Hemmer M (2014) Complexity of the general chromatic art gallery problem. In: Proceedings of 30th European Workshop on Computational Geometry (EuroCG 2014)"},{"key":"3379_CR15","doi-asserted-by":"crossref","unstructured":"Fekete SP, Friedrichs S, Hemmer M, Mitchell JBM, Schmidt C (2014) On the chromatic art gallery problem. In: CCCG","DOI":"10.1007\/s00453-014-9961-x"},{"key":"3379_CR16","doi-asserted-by":"crossref","unstructured":"Garey MR, Johnson DS, Stockmeyer L (1974) Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. ACM, pp 47\u201363","DOI":"10.1145\/800119.803884"},{"key":"3379_CR17","doi-asserted-by":"crossref","unstructured":"Ghosh SK (2010) Approximation algorithms for art gallery problems in polygons and terrains. In: International Workshop on Algorithms and Computation. Springer, Berlin, pp 21\u201334","DOI":"10.1007\/978-3-642-11440-3_3"},{"key":"3379_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.comgeo.2018.01.003","volume":"73","author":"F Hoffmann","year":"2018","unstructured":"Hoffmann F, Kriegel K, Suri S, Verbeek K, Willert M (2018) Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. Comput Geom 73:24\u201334","journal-title":"Comput Geom"},{"key":"3379_CR19","unstructured":"Hoorfar H, Mohades A (2015) Special guards in chromatic art gallery. In: European Conference on Computational Geometry"},{"key":"3379_CR20","doi-asserted-by":"crossref","unstructured":"Iwamoto C, Ibusuki T (2020) Computational complexity of the chromatic art gallery problem for orthogonal polygons. In: International Workshop on Algorithms and Computation. Springer, Berlin, pp 146\u2013157","DOI":"10.1007\/978-3-030-39881-1_13"},{"issue":"3","key":"3379_CR21","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"DE Knuth","year":"1992","unstructured":"Knuth DE, Raghunathan A (1992) The problem of compatible representatives. SIAM J Discrete Math 5(3):422\u2013427","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"3379_CR22","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 (1986) Computational complexity of art gallery problems. IEEE Trans Inf Theory 32(2):276\u2013282","journal-title":"IEEE Trans Inf Theory"},{"key":"3379_CR23","unstructured":"Levcopoulos C (1987) Heuristics for minimum decompositions of polygons. PhD thesis"},{"issue":"1\u20133","key":"3379_CR24","first-page":"69","volume":"81","author":"Y Liu","year":"1998","unstructured":"Liu Y, Morgana A, Simeone B (1998) A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl Math 81(1\u20133):69\u201391","journal-title":"Discrete Appl Math"},{"key":"3379_CR25","first-page":"102","volume":"6","author":"AM Martins","year":"2006","unstructured":"Martins AM, Bajuelos AL (2006) Vertex guards in a subclass of orthogonal polygons. Int J Comput Sci Netw Secur 6:102\u2013108","journal-title":"Int J Comput Sci Netw Secur"},{"issue":"2","key":"3379_CR26","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D Schuchardt","year":"1995","unstructured":"Schuchardt D, Hecker H-D (1995) Two NP-hard art-gallery problems for ortho-polygons. Math Logic Q 41(2):261\u2013267","journal-title":"Math Logic Q"},{"issue":"02","key":"3379_CR27","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"CJ Worman","year":"2007","unstructured":"Worman CJ, Keil M (2007) Polygon decomposition and the orthogonal art gallery problem. Int J Comput Geom Appl 17(02):105\u2013138","journal-title":"Int J Comput Geom Appl"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03379-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03379-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03379-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T23:26:27Z","timestamp":1626996387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03379-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,23]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["3379"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03379-8","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2020,7,23]]},"assertion":[{"value":"23 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}