The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by
Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the
shortest distances and paths between vertices with any given single failure in constant
time without reconstructing the oracle. Using their paper as a guideline, we have
implemented their algorithm in C++ and recorded each step in this thesis. Each step
has its own pseudo-code and its own analysis to prove that the entire oracle construction
stays within the stated running time and total space bounds, from the authors. The
effciency of the algorithm is compared against that of the brute-force methods total
running time and total space needed. Using multiple test cases with an increasing
number of vertices and edges, we have experimentally validated that their algorithm
holds true to their statements of space, running time, and query time.
| Identifer | oai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-4881 |
| Date | 26 October 2010 |
| Creators | Williams, Vincent Troy |
| Publisher | Scholar Commons |
| Source Sets | University of South Flordia |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Graduate Theses and Dissertations |
| Rights | default |
Page generated in 0.0018 seconds