Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2016.08.005 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Edge-colored graphs,Properly colored trails,Chinese Postman Problem,Polynomial-time algorithms | Journal | abs/1512.06283 |
Issue | ISSN | Citations |
P2 | 0166-218X | 3 |
PageRank | References | Authors |
0.38 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gregory Gutin | 1 | 1583 | 142.47 |
| Mark Jones | 2 | 25 | 7.09 |
| Bin Sheng | 3 | 6 | 1.77 |
| Magnus Wahlström | 4 | 401 | 33.04 |
| Anders Yeo | 5 | 1225 | 108.09 |