Feasibility of the Mixed Postman Problem with Restrictions on the Edges |
| |
| Institution: | 1. Department of Mechanical Engineering and Materials Science, Duke University, Durham, NC-27708, USA;2. Department of Electrical and Computer Engineering, University of Patras, Rio, Achaia-26500, Greece;1. Institut Charles Delaunay/LOSI – UMR CNRS 6281, Université de Technologie de Troyes, CS 42060, 12 rue Marie Curie, 10004 Troyes, France;2. LIMOS – UMR CNRS 6158, Université Blaise Pascal, Campus des Cézeaux, 63177 Aubière Cedex, France;1. Institución Universitaria Esumer, Medellín, Colombia, grid.441880.1;2. Molde University College, Molde, Norway, 0000 0004 0434 9525, grid.411834.b;3. UC Davis, Davis, CA, USA, 0000 0004 1936 9684, grid.27860.3b;1. University of Coimbra, CITTA, Department of Civil Engineering, Coimbra, Portugal;2. EIGeS – Research Centre in Industrial Engineering, Management and Sustainability, Faculty of Engineering, Universidade Lusófona, Lisboa, Portugal;3. Centre for Management Studies, Instituto Superior Técnico (CEG-IST), Universidade de Lisboa, Lisbon, Portugal |
| |
| Abstract: | The mixed postman problem consists of finding a minimum cost tour of a connected mixed graph traversing all its vertices, edges, and arcs at least once. We consider the variant of the mixed postman problem where all edges must be traversed exactly once. The feasibility version of this problem is NP-complete. We introduce an infinite class of necessary conditions for feasibility, which we conjecture are also sufficient. We prove that no finite subset of these conditions is sufficient. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
