Persistent Link:
http://hdl.handle.net/10150/291952
Title:
Diverse routing in network planning
Author:
Vohnout, Sonia Isabel, 1964-
Issue Date:
1990
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
This thesis discusses an algorithm and two heuristics for solving a particular network optimization problem: The node-disjoint paths problem. The goal of this optimization problem is to find two node-disjoint paths between a given origin-destination pair whose total cost is minimum. This problem is shown to be NP-Hard. Two heuristics are investigated in this thesis. The sequential shortest paths heuristic, is the faster of the two methods, but the quality of the solution may be sacrificed. On the other hand, the simultaneous shortest paths heuristic, which yields very good solutions, has higher complexity. We also discuss an implicit enumeration algorithm that is used to verify the quality of the solution obtained from the heuristics.
Type:
text; Thesis-Reproduction (electronic)
Keywords:
Operations Research.
Degree Name:
M.S.
Degree Level:
masters
Degree Program:
Graduate College; Systems and Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Sen, Suvrajeet

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleDiverse routing in network planningen_US
dc.creatorVohnout, Sonia Isabel, 1964-en_US
dc.contributor.authorVohnout, Sonia Isabel, 1964-en_US
dc.date.issued1990en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThis thesis discusses an algorithm and two heuristics for solving a particular network optimization problem: The node-disjoint paths problem. The goal of this optimization problem is to find two node-disjoint paths between a given origin-destination pair whose total cost is minimum. This problem is shown to be NP-Hard. Two heuristics are investigated in this thesis. The sequential shortest paths heuristic, is the faster of the two methods, but the quality of the solution may be sacrificed. On the other hand, the simultaneous shortest paths heuristic, which yields very good solutions, has higher complexity. We also discuss an implicit enumeration algorithm that is used to verify the quality of the solution obtained from the heuristics.en_US
dc.typetexten_US
dc.typeThesis-Reproduction (electronic)en_US
dc.subjectOperations Research.en_US
thesis.degree.nameM.S.en_US
thesis.degree.levelmastersen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSen, Suvrajeeten_US
dc.identifier.proquest1341290en_US
dc.identifier.bibrecord.b26341657en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.