Matching,Euler tours and the Chinese postman |
| |
Authors: | Jack Edmonds Ellis L. Johnson |
| |
Affiliation: | (1) University of Waterloo, Waterloo, Ontario, Canada;(2) IBM Watson Research Center, Yorktown Heights, New York, USA |
| |
Abstract: | The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|