Matching, Euler tours and the Chinese postman | Zendy

Jack Edmonds | Zendy; Ellis L. Johnson | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Matching, Euler tours and the Chinese postman

Author(s) -

Jack Edmonds,

Ellis L. Johnson

Publication year - 1973

Publication title -

mathematical programming

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 2.358

H-Index - 131

eISSN - 1436-4646

pISSN - 0025-5610

DOI - 10.1007/bf01580113

Subject(s) - polyhedron , mathematics , matching (statistics) , euler's formula , regular polygon , integer programming , integer (computer science) , convex hull , combinatorics , linear programming , algorithm , mathematical optimization , computer science , geometry , mathematical analysis , statistics , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research