This is a theoretical research paper of interest for experts in graph algorithms, particularly matching and postman tours. Its goal is to give a new setting for, or to revisit, such classics as the Chinese postman problem as originally dealt with by Guan [1] or the well-known matching algorithm of Edmonds, as approached by Lovász [2]. For this purpose, the author uses the concept of a t-join in an undirected graph. As he points out, t-joins are generalizations of postman tours, matchings, and paths. t-cuts are naturally associated with t-joins. The author’s main result is a polynomial-time combinatorial algorithm that determines a minimum t-join and a so-called canonical (maximum) packing of t-cuts.
A pertinent list of references is included in the paper. The paper will have appeal for those who are knowledgeable about the topic but will be difficult for the non-expert to read.