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.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/291952 |
| Date | January 1990 |
| Creators | Vohnout, Sonia Isabel, 1964- |
| Contributors | Sen, Suvrajeet |
| Publisher | The University of Arizona. |
| Source Sets | University of Arizona |
| Language | en_US |
| Detected Language | English |
| Type | text, Thesis-Reproduction (electronic) |
| 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. |
Page generated in 0.0021 seconds