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

165 Downloads (Pure)

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.

Original languageEnglish
JournalDiscrete Applied Mathematics
Volume217
Issue numberPart 2
Pages (from-to)196-202
ISSN0166-218X
DOIs
Publication statusPublished - 2017

Keywords

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

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

  • Cite this