Matching, Euler tours and the Chinese postman

1973/12/01 by Jack Edmonds, Ellis L. Johnson · 11 citations
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems #semigroups and automata theory

paper · doi:10.1007/bf01580113

crossref issued 1973/12/01 · crossref published 1973/12/01 · crossref published-print 1973/12/01 · openalex publication_date 1973/12/01 · crossref created 2005/04/28 · crossref deposited 2019/05/03 · openalex created_date 2025/10/10 · crossref indexed 2026/07/17 · openalex updated_date 2026/07/23

Citations

• Matching: A Well-Solved Class of Integer Linear Programs
• Networks and vehicle routing for municipal waste collection
• Paths, Trees, and Flowers

Cited by

• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Postman tour on a graph with precedence relation on arcs
• On the Windy Postman Problem on eulerian graphs
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Approximation Algorithms for Some Routing Problems
• A new algorithm for the directed chinese postman problem
• Expanding vertices to triangles in cubic graphs
• Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Arc routing [wikipedia]
• Mixed Chinese postman problem [wikipedia]