Complexity of Minimum Corridor Guarding Problems

Author

Ning Xu, CUNY City College

Date of Award

2011

Document Type

Thesis

Department

Computer Science

Keywords

Computational Geomery, Computational Complexity, Corridor Guarding

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"

Recommended Citation

Xu, Ning, "Complexity of Minimum Corridor Guarding Problems" (2011). CUNY Academic Works.
https://academicworks.cuny.edu/cc_etds_theses/30