Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Tomisawa, Masaki
Department of Life Engineering, Faculty of Engineering, Maebashi Institute of Technology, Maebashi city, Gunma, 371-0816, Japan
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Computational complexity of the police officer patrol problem on weighted digraphs Tomisawa, Masaki; Tohyama, Hiroaki
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 12, No 2 (2024): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2024.12.2.10

Abstract

A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph and 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. Given a graph G and a natural number k, the vertex cover problem is the problem of deciding whether there exists a vertex cover in G of size at most k. The vertex cover problem is one of Karp’s 21 NP-complete problems.Recently, we introduced an edge routing problem that 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. We showed that the problem of deciding whether there exists a patrol route for a given mixed graph in which each edge is either traversed exactly once or confirmed visually is NP-complete. In this paper, we show that the police officer patrol problem remains NP-complete even if given graphs are weighted digraphs.
Co-Authors Tohyama, Hiroaki