I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover in O(n^3) time. I know how to find it in O(n^6) time by creating a new graph with a vertex for every edge and using a perfect matching, but I have not been able to find an algorithm that runs in O(n^3) time. Does anyone know the algorithm or an accessible place where it is laid out?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.