Statistical mechanics of the travelling salesman on the Sierpinski gasket
- 1 January 1986
- journal article
- Published by EDP Sciences in Journal de Physique
- Vol. 47 (1) , 9-14
- https://doi.org/10.1051/jphys:019860047010900
Abstract
We study the statistical mechanics of the travelling salesman on a Sierpinski gasket in which the bond lengths { λi } are quenched random variables. The problem of finding the shortest closed path which visits all N sites is tractable if all the| λi — 1 | are less than (2 N + 1)-1. For a particular choice of the bond-length probability distribution and at low temperatures, the system behaves like a set of non-interacting Ising spins in a quenched random magnetic field. The relevance of one of our results to collapsed polymer chains in random media is also discussedKeywords
This publication has 11 references indexed in Scilit:
- Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithmJournal of Optimization Theory and Applications, 1985
- Configuration space analysis of travelling salesman problemsJournal de Physique, 1985
- An evaluation of the number of Hamiltonian pathsJournal de Physique Lettres, 1985
- Directed self-avoiding walks on a randomly dilute latticeJournal de Physique, 1985
- The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis AlgorithmSIAM Review, 1984
- On the statistical mechanics of optimization problems of the travelling salesman typeJournal de Physique Lettres, 1984
- Self-interacting self-avoiding walks on the Sierpinski gasketJournal de Physique Lettres, 1984
- Solvable Fractal Family, and Its Possible Relation to the Backbone at PercolationPhysical Review Letters, 1981
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman ProblemOperations Research, 1964
- A soluble self-avoiding walk problemPhysica, 1963