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: | Barvinok A.I. |
Keywords: | networks, graphs |
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