Route Inspection Problem - T-joins

T-joins

Let T be a subset of the vertex set of a graph. An edge set whose odd-degree vertices are the vertices in T is called a T-join. (In a connected graph, a T-join exists if and only if |T| is even.) The T-join problem is to find a smallest T-join. When T is the empty set, a smallest T-join leads to a solution of the postman problem. For any T, a smallest T-join necessarily consists of |T| paths, no two having an edge in common, that join the vertices of T in pairs. The paths will be such that the total length of all of them is as small as possible. A minimum T-join can be obtained using a weighted matching algorithm that uses O(n3) computational steps.