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

Mathematics and Applied Mathematics

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

15 Citations (Scopus)

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
DOIs	https://doi.org/10.1016/j.dam.2016.08.005
Publication status	Published - 30 Jan 2017

Keywords

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

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2016.08.005

Cite this

@article{489809e417c146a5aa0aa13887b33304,

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

note = "Publisher Copyright: {\textcopyright} 2016",

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

}

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

KW - Chinese Postman Problem

KW - Edge-colored graphs

KW - Polynomial-time algorithms

KW - Properly colored trails

UR - https://www.scopus.com/pages/publications/84995505996

U2 - 10.1016/j.dam.2016.08.005

DO - 10.1016/j.dam.2016.08.005

M3 - Article

AN - SCOPUS:84995505996

SN - 0166-218X

VL - 217

SP - 196

EP - 202

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Chinese Postman Problem on edge-colored multigraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this