Chinese Postman Problem on edge-colored multigraphs. / Gutin, Gregory; Jones, Mark; Sheng, Bin; Wahlstrom, Magnus; Yeo, Anders.

In: Discrete Applied Mathematics, Vol. 217, No. Part 2, 30.01.2017, p. 196-202.

Research output: Contribution to journalArticlepeer-review




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.
Original languageEnglish
Pages (from-to)196-202
Number of pages7
JournalDiscrete Applied Mathematics
Issue numberPart 2
Early online date11 Sep 2016
Publication statusPublished - 30 Jan 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26824724