z-logo
open-access-imgOpen Access
Spanning tree manipulation and the travelling salesman problem
Author(s) -
A. K. Obruca
Publication year - 1968
Publication title -
the computer journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.319
H-Index - 64
eISSN - 1460-2067
pISSN - 0010-4620
DOI - 10.1093/comjnl/10.4.374
Subject(s) - travelling salesman problem , spanning tree , minimum spanning tree , extension (predicate logic) , steiner tree problem , computer science , tree (set theory) , mathematical optimization , lin–kernighan heuristic , mathematics , combinatorics , 2 opt , algorithm , programming language
The reasonable assumption is made that the majority of lines appearing in a minimal spanning tree for any network also appear in an optimal solution to the corresponding travelling salesman problem. A technique is described of manipulating the tree, by means of deletions and additions of lines, into a chain and hence obtain a feasible solution. An extension is considered with regard to the minimal wiring problem.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom