Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin; Mark Jones; Bin Sheng; Magnus Wahlstrom; Anders Yeo

doi:10.1016/j.dam.2016.08.005

Chinese Postman Problem on edge-colored multigraphs

Gregory Gutin, Mark Jones, Bin Sheng, Magnus Wahlstrom, Anders Yeo

Research output: Contribution to journal › Article › peer-review

77 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
Pages (from-to)	196-202
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	217
Issue number	Part 2
Early online date	11 Sept 2016
DOIs	https://doi.org/10.1016/j.dam.2016.08.005
Publication status	Published - 30 Jan 2017

Access to Document

10.1016/j.dam.2016.08.005

Accepted ManuscriptAccepted author manuscript, 223 KBLicence: CC BY-NC-ND

Cite this

@article{7b902a1d6b1946a8a15952890d4a11ca,

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

author = "Gregory Gutin and Mark Jones and Bin Sheng and Magnus Wahlstrom and Anders Yeo",

year = "2017",

month = jan,

day = "30",

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 - Wahlstrom, Magnus

AU - Yeo, Anders

PY - 2017/1/30

Y1 - 2017/1/30

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.

U2 - 10.1016/j.dam.2016.08.005

DO - 10.1016/j.dam.2016.08.005

M3 - Article

SN - 0166-218X

VL - 217

SP - 196

EP - 202

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - Part 2

ER -