Chinese Postman Problem on Edge-Colored Multigraphs
classification
💻 cs.DS
math.CO
keywords
problemchinesegraphspostmandirectededge-coloredmultigraphsresult
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{7RNIIXQT}
Prints a linked pith:7RNIIXQT badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.