@article{ART002129597},
author={Sang-Un, Lee},
title={An Eulerian Cycle Algorithm for Chinese Postman Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2016},
volume={21},
number={7},
pages={47-52}
TY - JOUR
AU - Sang-Un, Lee
TI - An Eulerian Cycle Algorithm for Chinese Postman Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2016
VL - 21
IS - 7
PB - The Korean Society Of Computer And Information
SP - 47
EP - 52
SN - 1598-849X
AB - This paper introduces an algorithm to construct an Eulerian cycle for Chinese postman problem.
The Eulerian cycle is formed only when all vertices in the graph have an even degree. Among available algorithms to the Eulerian cycle problem, Edmonds-Johnson’s stands out as the most efficient of its kind. This algorithm constructs a complete graph composed of shortest path between odd-degree vertices and derives the Eulerian cycle through minimum-weight complete matching method, thus running in . On the contrary, the algorithm proposed in this paper selects minimum weight edge from edges incidental to each vertex and derives the minimum spanning tree (MST) so as to finally obtain the shortest-path edge of odd-degree vertices. The algorithm not only runs in simple linear time complexity log but also obtains the optimal Eulerian cycle, as the implementation results on 4 different graphs concur.
KW - Chinese postman problem;Eulerian cycle;Degree;Minimum Weighted edge
DO -
UR -
ER -
Sang-Un, Lee. (2016). An Eulerian Cycle Algorithm for Chinese Postman Problem. Journal of The Korea Society of Computer and Information, 21(7), 47-52.
Sang-Un, Lee. 2016, "An Eulerian Cycle Algorithm for Chinese Postman Problem", Journal of The Korea Society of Computer and Information, vol.21, no.7 pp.47-52.
Sang-Un, Lee "An Eulerian Cycle Algorithm for Chinese Postman Problem" Journal of The Korea Society of Computer and Information 21.7 pp.47-52 (2016) : 47.
Sang-Un, Lee. An Eulerian Cycle Algorithm for Chinese Postman Problem. 2016; 21(7), 47-52.
Sang-Un, Lee. "An Eulerian Cycle Algorithm for Chinese Postman Problem" Journal of The Korea Society of Computer and Information 21, no.7 (2016) : 47-52.
Sang-Un, Lee. An Eulerian Cycle Algorithm for Chinese Postman Problem. Journal of The Korea Society of Computer and Information, 21(7), 47-52.
Sang-Un, Lee. An Eulerian Cycle Algorithm for Chinese Postman Problem. Journal of The Korea Society of Computer and Information. 2016; 21(7) 47-52.
Sang-Un, Lee. An Eulerian Cycle Algorithm for Chinese Postman Problem. 2016; 21(7), 47-52.
Sang-Un, Lee. "An Eulerian Cycle Algorithm for Chinese Postman Problem" Journal of The Korea Society of Computer and Information 21, no.7 (2016) : 47-52.
