Computational complexity of the police officer patrol problem on weighted digraphs

DOI10.5614/EJGTA.2024.12.2.10MaRDI QIDQ6669822zbMATH OpenFDO

Authors Masaki Tomisawa, Hiroaki Tohyama

Publication date 22 January 2025

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.5614/EJGTA.2024.12.2.10

zbMATH Keywords

Chinese postman problemedge traversingNP-completenesspolice officer patrol problemvertex cover problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• The guarding problem -- complexity and approximation
• On the Circuit Cover Problem for Mixed Graphs
• A minimum cost network flow model for the maximum covering and patrol routing problem
• Computational complexity of covering cyclic graphs
• Approximation Algorithms for Edge-Covering Problem

Cites work

• Matching, Euler tours and the Chinese postman
• On general routing problems
• On the complexity of edge traversing
• Reducibility among combinatorial problems
• The complexity of theorem-proving procedures
• The Rectilinear Steiner Tree Problem is NP-Complete

This page was built for publication: Computational complexity of the police officer patrol problem on weighted digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6669822)