Master of Science in Computer Science
First Committee Member
Second Committee Member
Third Committee Member
Graduate Faculty Representative
Number of Pages
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.
Computer algorithms; Graph algorithms; Graph theory
Koganti, Reshma, "Detours admitting short paths" (2010). UNLV Theses, Dissertations, Professional Papers, and Capstones. 888.