Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin; Mark Jones; Bin Sheng; Magnus Wahlström; Anders Yeo

doi:10.1016/j.dam.2016.08.005

Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin^*, Mark Jones, Bin Sheng, Magnus Wahlström, Anders Yeo

^*Corresponding author for this work

Department of Mathematics and Computer Science (IMADA)

Research output: Contribution to journal › Journal article › Research › peer-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 language	English
Journal	Discrete Applied Mathematics
Volume	217
Issue number	Part 2
Pages (from-to)	196-202
ISSN	0166-218X
DOIs	https://doi.org/10.1016/j.dam.2016.08.005
Publication status	Published - 2017

Keywords

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

Documents & Links

10.1016/j.dam.2016.08.005

Chinese Postman Problem on edge-colored multigraphsSubmitted manuscript, 147 KB

https://arxiv.org/pdf/1512.06283.pdf

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

Cite this

Gutin, G., Jones, M., Sheng, B., Wahlström, M., & Yeo, A. (2017). Chinese Postman Problem on edge-colored multigraphs. Discrete Applied Mathematics, 217(Part 2), 196-202. https://doi.org/10.1016/j.dam.2016.08.005

@article{22f9b0834f1644d5a2c4d598d58945ff,

title = "Chinese Postman Problem on edge-colored multigraphs",

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.",

keywords = "Chinese Postman Problem, Edge-colored graphs, Polynomial-time algorithms, Properly colored trails",

author = "Gregory Gutin and Mark Jones and Bin Sheng and Magnus Wahlstr{\"o}m and Anders Yeo",

year = "2017",

doi = "10.1016/j.dam.2016.08.005",

language = "English",

volume = "217",

pages = "196--202",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "Part 2",

}

TY - JOUR

T1 - Chinese Postman Problem on edge-colored multigraphs

AU - Gutin, Gregory

AU - Jones, Mark

AU - Sheng, Bin

AU - Wahlström, Magnus

AU - Yeo, Anders

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Chinese Postman Problem

KW - Edge-colored graphs

KW - Polynomial-time algorithms

KW - Properly colored trails

U2 - 10.1016/j.dam.2016.08.005

DO - 10.1016/j.dam.2016.08.005

M3 - Journal article

AN - SCOPUS:84995505996

VL - 217

SP - 196

EP - 202

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - Part 2

ER -