Award Date

8-2010

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi Gewali

Second Committee Member

John Minor

Third Committee Member

Yoohwan Kim

Graduate Faculty Representative

Rama Venkat

Number of Pages

49

Abstract

Finding shortest paths between two vertices in a weighted graph is a well explored problem and several efficient algorithms for solving it have been reported. We propose a new variation of this problem which we call the Detour Admitting Shortest Path Problem (DASPP).We present an efficient algorithm for solving DASPP. This is the first algorithm that constructs a shortest path such that each edge of the shortest path admits a detour with no more than k−hops. This algorithm has important applications in transportation networks. We also present implementation issues for the detour admitting shortest path algorithm.

Keywords

Computer algorithms; Graph algorithms; Graph theory

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS