Abstract
dc:descriptionThe 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.
Degree
thesis:*- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science and Engineering
- Grantor
- University of South Florida
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Williams, Vincent Troy
- Contributors dc:contributor
-
- Rahul Tripathi, Ph.D.
- Lawrence O. Hall, Ph.D.
- Sudeep Sarkar, Ph.D.
Subjects
dc:subject × 3Rights
- Language dc:language
- EN-US
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/3697