Back to search

University of South Florida

An Experimental Study of Distance Sensitivity Oracles

Abstract

dc:description

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.

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 × 3

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/3697

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Williams, Vincent Troy. An Experimental Study of Distance Sensitivity Oracles. Thesis thesis, University of South Florida, 2010. https://digitalcommons.usf.edu/etd/3697