The directed Chinese postman problem

Abstract

The Chinese Postman Problem on weighted directed multigraphs has many applications, including analysing interactive system and web site usability. Clear algorithms for the problem are not available. This paper derives an algorithm, which is presented as a complete, executable Java class, and it shows that no significantly more efficient algorithm is possible. The paper also solves a generalisation, the directed Rural Chinese Postman.