2006/09/01 by Zaragoza Martinez, Francisco Javier · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems
paper · doi:10.1109/iceee.2006.251877
openalex publication_date 2006/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The mixed postman problem consists of finding a minimum cost tour of a mixed graph traversing all its vertices, edges, and arcs at least once. We consider the variant of the mixed postman problem where all arcs must be traversed exactly once. We prove that the decision version of this problem is NP-complete. We give an integer programming formulation of this problem and we prove that one of its linear relaxations defines an integral polyhedron and can be solved in polynomial time