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
Mazzella, Daniel, "Disjoint paths in geometric graphs" (2005). UNLV Retrospective Theses & Dissertations. 2019.