5
$\begingroup$

I have a graph of Points G(V,E) and I want to find the shortest path covering all the edge, I want the minimum number of edge repetitions . Which is the best way to reduce this problem to well know problems like TSP , Hamiltonian circuit , Hamltonian completion ?

Thank you.

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ Well, all you need is to take care of vertices of odd degree: you have to split all of them but 2 into pairs and joint the pairs so that the total length is minimal. That is exactly the optimal matching problem, which certainly belongs to the category of "well-known". $\endgroup$
    – fedja
    Commented Jul 17, 2011 at 12:05

1 Answer 1

Reset to default
5
$\begingroup$

That is Chinese Postman Path. Search for Chinese Postman Problem...

E.g., this section from some book looks comprehensive: http://ie454.cankaya.edu.tr/uploads/files/Chp-03%20044-064.pdf

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .