A Note on the Traveling Salesman Problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Jan 1977 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Applied Mathematics, volume 32, pages 220-222 (issn: 0036-1399, eissn: 1095-712X,

Copyright policy )

Authors: Jones, Lee;

doi: 10.1137/0132019

A Note on the Traveling Salesman Problem

- Summary
- Subjects
- Metrics

Abstract

It is shown that the “shortest” directed Hamiltonian tour in a graph G with metrically realizable distances has the property that between any vertex and its nearest neighbor in that tour there must be a vertex $v_0 $ from which the succeeding arc in the tour is no more than twice as long as the shortest arc from $v_0 $ in G Some related results and conjectures are described.

Keywords

Extremal problems in graph theory, Integer programming

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average