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

dc.contributor.authorLevinton, Ira Rayen
dc.contributor.departmentIndustrial Engineering and Operations Researchen
dc.date.accessioned2016-02-01T14:45:18Zen
dc.date.available2016-02-01T14:45:18Zen
dc.date.issued1978en
dc.description.abstractThe 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.en
dc.description.degreeMaster of Scienceen
dc.format.extent147 leavesen
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttp://hdl.handle.net/10919/64663en
dc.language.isoen_USen
dc.publisherVirginia Polytechnic Institute and State Universityen
dc.relation.isformatofOCLC# 20742204en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1978.L49en
dc.subject.lcshHamiltonian systemsen
dc.subject.lcshGraph theoryen
dc.titleA decomposition procedure for finding the minimal Hamiltonian chain of a sparse graphen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineIndustrial Engineering and Operations Researchen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
LD5655.V855_1978.L49.pdf
Size:
2.66 MB
Format:
Adobe Portable Document Format
Collections