- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Shortest paths on uncertain terrains
Open Collections
UBC Theses and Dissertations
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 | |
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 | |
Type | |
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 | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2004-11
|
Campus | |
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.