P108: Enumeration of $k$ best solutions to the Chinese postman problem solutions
P108: Enumeration of $k$ best solutions to the Chinese postman problem solutions
Input:
A graph $G = (V, E)$.
Output:
$K$ best solutions to the Chinese postman problem.
Complexity:
$O(S( n,m ) + K( n + m + \log k + nT( n + m,m ) ) )$ where $S( s,t )$ denotes the time complexity of an algorithm for ordinary Chinese postman problems and $T( s,t )$ denotes the time complexity of a post-optimal algorithm for non-bipartite matching problems defined on a graph with s vertices and t edges.