| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949792 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
It is well-known that the Chinese Postman Problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in sharp contrast to the Chinese Postman Problem on mixed graphs, i.e., graphs with directed and undirected edges, for which the problem is NP-hard.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory Gutin, Mark Jones, Bin Sheng, Magnus Wahlström, Anders Yeo,