Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin*, Mark Jones, Bin Sheng, Magnus Wahlström, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

149 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
JournalDiscrete Applied Mathematics
Issue numberPart 2
Pages (from-to)196-202
Publication statusPublished - 2017


  • Chinese Postman Problem
  • Edge-colored graphs
  • Polynomial-time algorithms
  • Properly colored trails


Dive into the research topics of 'Chinese Postman Problem on edge-colored multigraphs'. Together they form a unique fingerprint.

Cite this