Two algorithmic results for the traveling salesman problem

Two algorithmic results for the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20041853
Country: United States
Volume: 21
Issue: 1
Start Page Number: 65
End Page Number: 84
Publication Date: Feb 1996
Journal: Mathematics of Operations Research
Authors:
Keywords: networks, graphs
Abstract:

For any norm in a Euclidean space and for any number δ>0 we present a polynomial time algorithm which computes a Hamiltonian circuit with the given vertices in the space whose length approximates, with relative error less than delta, the largest length of a Hamiltonian circuit with these vertices. We also present an algorithm which for a given graph with n vertices computes the number of Hamiltonian circuits in this graph with 2n+0(log(n), time complexity and a polynomial in n space complexity. As a by-product of our approach we prove that the permanent of a matrix can be computed in polynomial time provided the rank of the matrix is fixed.

Reviews

Required fields are marked *. Your email address will not be published.