Matching,Euler tours and the Chinese postman |
| |
| Authors: | Jack Edmonds Ellis L Johnson |
| |
| Institution: | (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 等数据库收录！ |
|
