0
$\begingroup$

Multiple people suggest that the Chinese Postman Problem (also referred to as the Route Inspection Problem) of a graph G can be solved by applying the Traveling Salesman Problem to its line graph L(G). However, I find no evidence of that in literature and initial tests suggest that it is not possible.

Can anyone confirm the statement and/or provide additional and more specific information/examples on how to do it?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.