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 language | English |
---|---|
Journal | Discrete Applied Mathematics |
Volume | 217 |
Issue number | Part 2 |
Pages (from-to) | 196-202 |
ISSN | 0166-218X |
DOIs | |
Publication status | Published - 2017 |
Keywords
- Chinese Postman Problem
- Edge-colored graphs
- Polynomial-time algorithms
- Properly colored trails