Back to results
City University of New York - City College
Complexity of Minimum Corridor Guarding Problems
Abstract
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"
Degree
thesis:*- Name thesis:degree_name
- Master of Science (M.S.)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science
- Year
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Xu, Ning
Subjects
dc:subject × 5Identifiers
dc:identifier.*- Repository record dc:identifier
- https://academicworks.cuny.edu/cc_etds_theses/30
- OAI identifier oai:identifier
- oai:academicworks.cuny.edu:cc_etds_theses-1029