{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:24:18Z","timestamp":1725553458262},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540340706"},{"type":"electronic","value":"9783540340713"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11751540_18","type":"book-chapter","created":{"date-parts":[[2006,5,10]],"date-time":"2006-05-10T12:28:51Z","timestamp":1147264131000},"page":"161-170","source":"Crossref","is-referenced-by-count":1,"title":["Fault Tolerant Guarding of Grids"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Kosowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Ma\u0142afiejski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"\u017byli\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Contemporary Mathematics series 352","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/conm\/352\/10","volume-title":"Graph Colorings","author":"J. Bia\u0142ogrodzki","year":"2004","unstructured":"Bia\u0142ogrodzki, J.: Path Coloring and Routing in Graphs. In: Kubale, M. (ed.) Graph Colorings. Contemporary Mathematics series 352, pp. 139\u2013152. AMS, Providence (2004)"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-46648-7_35","volume-title":"Graph Drawing","author":"N. Castro de","year":"1999","unstructured":"de Castro, N., Cobos, F.J., Dana, J.C., M\u00e1rquez, A., Noy, M.: Triangle-free planar graphs as segments intersection graphs. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 341\u2013358. Springer, Heidelberg (1999)"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. Journal of the ACM\u00a039, 1\u201354 (1992)","journal-title":"Journal of the ACM"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(98)00046-5","volume":"66","author":"J. Czy\u017cowicz","year":"1998","unstructured":"Czy\u017cowicz, J., Kranakis, E., Urrutia, J.: A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments. Information Processing Letters\u00a066, 125\u2013126 (1998)","journal-title":"Information Processing Letters"},{"key":"18_CR5","unstructured":"Dangelmayr, C.: Intersection graphs of straight-line segments. In: 4th Annual CGC Workshop on Computational Geometry, Stels (2004)"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"M.E. Dyer","year":"1986","unstructured":"Dyer, M.E., Frieze, A.M.: Planar 3DM is NP-complete. Journal of Algorithms\u00a07, 174\u2013184 (1986)","journal-title":"Journal of Algorithms"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-45753-4_11","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"U. Feige","year":"2002","unstructured":"Feige, U., Ofek, E., Wieder, U.: Approximating Maximum Edge Coloring in Multigraphs. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 108\u2013121. Springer, Heidelberg (2002)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Finke, U., Hinchirs, K.: Overlaying simply connected planar subdivisions in linear time. In: Proc. ACM SoCG, pp. 119\u2013126 (1995)","DOI":"10.1145\/220279.220292"},{"key":"18_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York (1979)"},{"key":"18_CR10","first-page":"211","volume-title":"Handbook of Combinatorics","author":"R.L. Graham","year":"1995","unstructured":"Graham, R.L., Groetschel, M., Lovasz, L.: Handbook of Combinatorics, vol.\u00a01, pp. 211\u2013212. Elsevier, Amsterdam (1995)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"I.B.-A. Hartman","year":"1991","unstructured":"Hartman, I.B.-A., Newman, I., Ziv, R.: On grid intersection graphs. Discrete Mathematics\u00a087, 41\u201352 (1991)","journal-title":"Discrete Mathematics"},{"key":"18_CR12","first-page":"718","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-colouring, SIAM. Journal of Computing\u00a010, 718\u2013720 (1981)","journal-title":"Journal of Computing"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1006\/jagm.2000.1121","volume":"37","author":"D.P. Jacobs","year":"2000","unstructured":"Jacobs, D.P., Jamison, R.E.: Complexity of recognizing equal unions in families of sets. Journal of Algorithms\u00a037, 495\u2013504 (2000)","journal-title":"Journal of Algorithms"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1002\/jgt.10022","volume":"39","author":"K. Kawarabayashi","year":"2002","unstructured":"Kawarabayashi, K., Matsuda, H., Oda, Y., Ota, K.: Path factors in cubic graphs. Journal of Graph Theory\u00a039, 188\u2013193 (2002)","journal-title":"Journal of Graph Theory"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D. K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann.\u00a077, 453\u2013465 (1916)","journal-title":"Math. Ann."},{"key":"18_CR16","unstructured":"Liaw, B.C., Huang, N.F., Lee, R.C.T.: The minimum cooperative guards problem on k-spiral polygons. In: Proc. CCCG 1993, pp. 97\u2013101 (1993)"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0020-0190(94)00128-6","volume":"52","author":"B.C. Liaw","year":"1994","unstructured":"Liaw, B.C., Lee, R.C.T.: An optimal algorithm to solve the minimum weakly cooperative guards problem for 1-spiral polygons. Information Processing Letters\u00a052, 69\u201375 (1994)","journal-title":"Information Processing Letters"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/11424758_68","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2005","author":"M. Ma\u0142afiejski","year":"2005","unstructured":"Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Weakly cooperative guards in grids. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Lagan\u00e1, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol.\u00a03480, pp. 647\u2013656. Springer, Heidelberg (2005)"},{"key":"18_CR19","unstructured":"Nierhoff, T., \u017byli\u0144ski, P.: Cooperative guards in grids. In: 3rd Annual CGC Workshop on Computational Geometry, Neustrelitz (2003)"},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(86)90050-5","volume":"23","author":"S. Ntafos","year":"1986","unstructured":"Ntafos, S.: On gallery watchmen in grids. Information Processing Letters\u00a023, 99\u2013102 (1986)","journal-title":"Information Processing Letters"},{"key":"18_CR21","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, Oxford (1987)"},{"key":"18_CR22","unstructured":"Scheinerman, E.R.: Intersection classes and multiple intersection parameters of graphs, PhD thesis. Princenton University (1984)"},{"key":"18_CR23","volume-title":"Handbook on Computational Geometry","author":"J. Urrutia","year":"2000","unstructured":"Urrutia, J.: Art Gallery and Illumination Problems. In: Handbook on Computational Geometry. Elsevier Science, Amsterdam (2000)"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications - ICCSA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11751540_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:57:44Z","timestamp":1619506664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11751540_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540340706","9783540340713"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11751540_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}