Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin, Mark Jones, Bin Sheng, Magnus Wahlstrom, Anders Yeo

Research output: Contribution to journalArticlepeer-review

74 Downloads (Pure)


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 Sept 2016
Publication statusPublished - 30 Jan 2017

Cite this