Open Collections

UBC Theses and Dissertations

UBC Theses Logo
Featured Collection

UBC Theses and Dissertations

Shortest paths on uncertain terrains Gray, Chris

Abstract

In this dissertation, we introduce the concept of uncertain terrains first suggested by Jorg Sack. We then examine the problem of finding the shortest path that stays on these terrains given certain assumptions about the terrains. We show that this problem is NP-hard under two fairly natural assumptions (meaning that we do not expect any polynomial time algorithm that finds these paths to be discovered).

Item Metadata

Title
Shortest paths on uncertain terrains
Creator
Gray, Chris
Publisher
University of British Columbia
Date Issued
2004
Description
In this dissertation, we introduce the concept of uncertain terrains first suggested by Jorg Sack. We then examine the problem of finding the shortest path that stays on these terrains given certain assumptions about the terrains. We show that this problem is NP-hard under two fairly natural assumptions (meaning that we do not expect any polynomial time algorithm that finds these paths to be discovered).
Extent
1417272 bytes
Genre
Thesis/Dissertation
Type
Text
File Format
application/pdf
Language
eng
Date Available
2009-11-24
Provider
Vancouver : University of British Columbia Library
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
DOI
10.14288/1.0051736
URI
http://hdl.handle.net/2429/15691
Degree
Master of Science - MSc
Program
Computer Science
Affiliation
Science, Faculty of; Computer Science, Department of
Degree Grantor
University of British Columbia
Graduation Date
2004-11
Campus
UBCV
Scholarly Level
Graduate
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.