Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to design a branch-and bound algorithm that solves the optimal tour of a graph on the cartesian plane every time. I have been given the hint that identifying hopeless branches earlier in the runtime will compound into a program that runs "a hundred times faster". I had the idea of assuming that the shortest edge connected to the starting/ending node will be either the first or last edge in the tour but a thin diamond shaped graph proves otherwise. Does any one have ideas for how to eliminate these hopeless branches or a reference that talks about this?

share|improve this question
    
Cross posted at cstheory.stackexchange.com/questions/14508/… –  Paresh Nov 27 '12 at 18:56
    
You should only post on one site at a time. If an acceptable answer is not found there, then flag the moderators to migrate the question to another site. Please choose one site and delete the question from the others. –  robjohn Nov 27 '12 at 21:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.