{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/64663"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/64663","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"A decomposition procedure for finding the minimal Hamiltonian chain of a sparse graph","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Levinton, Ira Ray"],"institution":"Virginia Polytechnic Institute and State University","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Industrial Engineering and Operations Research","degree_department":"Industrial Engineering and Operations Research","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1978,"date_issued":"1978","date_published":"1978","updated_at":"2026-07-22T22:19:37Z","subjects":[],"languages":["en_US"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10919/64663","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Industrial Engineering and Operations Research"]},{"key":"dc:creator","label":"Author","values":["Levinton, Ira Ray"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-02-01T14:45:18Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-02-01T14:45:18Z"]},{"key":"dc:date.issued","label":"Date","values":["1978"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Polytechnic Institute and State University"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering and Operations Research"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/64663"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A decomposition procedure for finding the minimal Hamiltonian chain of a sparse graph"]}]}],"canonical_facts":{"dc:contributor.department":["Industrial Engineering and Operations Research"],"dc:creator":["Levinton, Ira Ray"],"dc:date.accessioned":["2016-02-01T14:45:18Z"],"dc:date.available":["2016-02-01T14:45:18Z"],"dc:date.issued":["1978"],"dc:description.abstract":["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."],"dc:description.degree":["Master of Science"],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10919/64663"],"dc:language.iso":["en_US"],"dc:publisher":["Virginia Polytechnic Institute and State University"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["A decomposition procedure for finding the minimal Hamiltonian chain of a sparse graph"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Industrial Engineering and Operations Research"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:37Z"}