Return to search

A decomposition procedure for finding the minimal Hamiltonian chain of a sparse graph

The problem considered here is one of finding the minimal Hamiltonian chain of a graph. A single chain must traverse all 𝑛 vertices of a graph with the minimal distance. The proposed procedure reduces a large problem into several smaller problems and uses a branch and bound algorithm to find the minimal Hamiltonian chain of each partitioned subproblem.

The graph is decomposed and partitioned into subproblems with the use of necessary conditions for the existence of a Hamiltonian chain. This process is only applicable to graphs with relatively few incident edges per vertex.

The branch and bound algorithm makes use of concepts developed by Nicos Christofides. Hamiltonian chains are derived by using minimal spanning trees. / Master of Science

Identiferoai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/64663
Date January 1978
CreatorsLevinton, Ira Ray
ContributorsIndustrial Engineering and Operations Research
PublisherVirginia Polytechnic Institute and State University
Source SetsVirginia Tech Theses and Dissertation
Languageen_US
Detected LanguageEnglish
TypeThesis, Text
Format147 leaves, application/pdf, application/pdf
RightsIn Copyright, http://rightsstatements.org/vocab/InC/1.0/
RelationOCLC# 20742204

Page generated in 0.0019 seconds