Re:The TSP Isn't NP Complete
by ufo on Monday December 30, 2013 @07:24PM
(#6988102)
Removing one edge at a time won't work if there is a second, redundant, optimal path (every edge can be removed without altering the cost). I don't remember how you get around this but it shouldnt be too complicated...
[ Parent
| on HN ]
Re:The TSP Isn't NP Complete
by ColinWright on Tuesday December 31, 2013 @03:42AM
(#6989656)
Sorry, thought that was clear. If you remove an edge and find the cost doesn't change, don't put the edge back - carry on with the smaller graph.