Master of Science (MS)
First Committee Member
Laxmi P. Gewali
Number of Pages
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.
Disjoint; Geometric; Graphs; Paths
University of Nevada, Las Vegas
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 email@example.com and include clear identification of the work, preferably with URL.
Mazzella, Daniel, "Disjoint paths in geometric graphs" (2005). UNLV Retrospective Theses & Dissertations. 2019.
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/