{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T19:12:16Z","timestamp":1723662736471},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p> Given a set \u2112 of non-parallel lines in the plane and a nonempty subset \u2112\u2032 \u2286 \u2112, a guarding tree for \u2112\u2032 is a tree contained in the union of the lines in \u2112 such that if a mobile guard (agent) runs on the edges of the tree, all lines in \u2112\u2032 are visited by the guard. Similarly, given a connected arrangement \ud835\udcae of line segments in the plane and a nonempty subset \ud835\udcae\u2032 \u2286 \ud835\udcae, we define a guarding tree for \ud835\udcae\u2032. The minimum guarding tree problem for a given set of lines or line segments is to find a minimum-length guarding tree for the input set. We provide a simple alternative (to [N. Xu, Complexity of minimum corridor guarding problems, Inf. Process. Lett.112(17\u201318) (2012) 691\u2013696.]) proof of the problem of finding a guarding tree of minimum length for a set of orthogonal (axis-parallel) line segments in the plane. Then, we present two approximation algorithms with factors 2 and 3.98, respectively, for computing a minimum guarding tree for a subset of a set of n arbitrary non-parallel lines in the plane; their running times are O(n<jats:sup>8<\/jats:sup>) and O(n<jats:sup>6<\/jats:sup> log n), respectively. Finally, we show that this problem is NP-hard for lines in 3-space. <\/jats:p>","DOI":"10.1142\/s1793830914500116","type":"journal-article","created":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T20:59:09Z","timestamp":1383166749000},"page":"1450011","source":"Crossref","is-referenced-by-count":3,"title":["THE MINIMUM GUARDING TREE PROBLEM"],"prefix":"10.1142","volume":"06","author":[{"given":"ADRIAN","family":"DUMITRESCU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin\u2013Milwaukee, Milwaukee, WI 53211, USA"}]},{"given":"JOSEPH S. B.","family":"MITCHELL","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, NY 11794-3600, USA"}]},{"given":"PAWEL","family":"\u017bYLI\u0143SKI","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Gda\u0144sk, 80-952 Gda\u0144sk, Poland"}]}],"member":"219","published-online":{"date-parts":[[2014,2,18]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.05.001"},{"key":"rf2","first-page":"139","volume":"15","author":"Bose P.","journal-title":"Dicrete Math. Theoretical Computer Sci."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.014"},{"key":"rf5","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2009"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.11.008"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90013-V"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.10.002"},{"key":"rf15","first-page":"56","volume":"6","author":"Gonzalez-Gutierrez A.","journal-title":"ACM Trans. Algorithms"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.002"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90050-5"},{"key":"rf22","volume-title":"Art Gallery Theorems and Algorithms","author":"O'Rourke J.","year":"1987"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00057-8"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2797-9"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.06.003"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830914500116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:59:28Z","timestamp":1565099968000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830914500116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,18]]},"references-count":22,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2014,2,18]]},"published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1142\/S1793830914500116"],"URL":"https:\/\/doi.org\/10.1142\/s1793830914500116","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,18]]}}}