@article{oai:ipsj.ixsq.nii.ac.jp:00217713,
 author = {Hiroaki, Tohyama and Masaki, Tomisawa and Hiroaki, Tohyama and Masaki, Tomisawa},
 issue = {4},
 journal = {情報処理学会論文誌},
 month = {Apr},
 note = {We introduce an edge routing decision problem called the police officer patrol problem (POPP), which is related to the vertex cover problem. A vertex cover of a graph can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. In the edge routing problem we consider, a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. In this paper, we show that the POPP on mixed graphs is NP-complete.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.30(2022) (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.30.307
------------------------------, We introduce an edge routing decision problem called the police officer patrol problem (POPP), which is related to the vertex cover problem. A vertex cover of a graph can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. In the edge routing problem we consider, a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. In this paper, we show that the POPP on mixed graphs is NP-complete.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.30(2022) (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.30.307
------------------------------},
 title = {Complexity of the Police Officer Patrol Problem},
 volume = {63},
 year = {2022}
}