{"id":{"repo_id":"cuny","oai_identifier":"oai:academicworks.cuny.edu:cc_etds_theses-1029"},"canonical_url":"https://search.dev.ndltd.org/etd/cuny/oai:academicworks.cuny.edu:cc_etds_theses-1029","repository":{"repo_id":"cuny","name":"City University of New York - City College","base_url":"https://academicworks.cuny.edu/do/oai/"},"display":{"title":"Complexity of Minimum Corridor Guarding Problems","abstract":"\"In this paper, the complexity of minimum corridor guarding problems is discussed. These problem can be described as: given a connected orthogo-nal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed tour with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed tour, all line segments are visited by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete\"","abstract_html":""In this paper, the complexity of minimum corridor guarding problems is discussed. These problem can be described as: given a connected orthogo-nal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed tour with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed tour, all line segments are visited by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete"","abstract_has_math":false,"creators":["Xu, Ning"],"institution":null,"degree_name":"Master of Science (M.S.)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-01-01T08:00:00Z","date_published":"2011-01-01T08:00:00Z","updated_at":"2026-07-24T01:56:34Z","subjects":["Computational Geomery","Computational Complexity","Corridor Guarding","Computer Sciences","Physical Sciences and Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://academicworks.cuny.edu/cc_etds_theses/30","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Xu, Ning"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.S.)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Geomery","Computational Complexity","Corridor Guarding","Computer Sciences","Physical Sciences and Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://academicworks.cuny.edu/cc_etds_theses/30"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["\"In this paper, the complexity of minimum corridor guarding problems is discussed. These problem can be described as: given a connected orthogo-nal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed tour with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed tour, all line segments are visited by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete\""]},{"key":"dc:title","label":"Title","values":["Complexity of Minimum Corridor Guarding Problems"]}]}],"canonical_facts":{"dc:creator":["Xu, Ning"],"dc:description.abstract":["\"In this paper, the complexity of minimum corridor guarding problems is discussed. These problem can be described as: given a connected orthogo-nal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed tour with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed tour, all line segments are visited by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete\""],"dc:identifier":["https://academicworks.cuny.edu/cc_etds_theses/30"],"dc:subject":["Computational Geomery","Computational Complexity","Corridor Guarding","Computer Sciences","Physical Sciences and Mathematics"],"dc:title":["Complexity of Minimum Corridor Guarding Problems"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (M.S.)"]},"updated_at":"2026-07-24T01:56:34Z"}