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 journal › Article
Published
Documents
- Accepted Manuscript
Accepted author manuscript, 223 KB, PDF document
Licence: CC BY-NC-ND Show licence
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 |
|---|---|
| Pages (from-to) | 196-202 |
| Number of pages | 7 |
| Journal | Discrete Applied Mathematics |
| Volume | 217 |
| Issue number | Part 2 |
| Early online date | 11 Sep 2016 |
| DOIs | |
| Publication status | Published - 30 Jan 2017 |
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
ID: 26824724