Award Date

1-1-2005

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Laxmi P. Gewali

Number of Pages

60

Abstract

Construction of the shortest paths connecting two given nodes in a geometric graph is the quintessential problem in computational geometry. We consider several variations of this problem with applications that include robotics, Geographic Information Systems, and sensor networks. The first problem we address is the development of an efficient algorithm for constructing a pair of short node-disjoint paths connecting start and target nodes. The second problem investigated is the development of efficient algorithms for constructing narrow and in-range broadcast corridors in triangulated geometric graphs. Finally, we consider the development of an approximation algorithm for constructing reduced overlap trees in three-colored geometric graphs. Theoretical analysis and a detailed experimental investigation of the proposed algorithms are also presented.

Keywords

Disjoint; Geometric; Graphs; Paths

Controlled Subject

Computer science

File Format

pdf

File Size

1546.24 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

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

Download


COinS