Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


kent1259182746.pdf (438.94 KB)

ETD Abstract Container

Abstract Header

Parallel and Network Algorithms and Applications for Steiner Trees and Voronoi Diagram

Muhammad, Rashid Bin
http://rave.ohiolink.edu/etdc/view?acc_num=kent1259182746

Abstract Details

2009, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
The thesis studied the algorithmic issues in the design and analysis of parallel and distributed geometric algorithms. In particular, the thesis presented our results on the parallel Steiner trees, the parallel Voronoi diagram, distributed range assignment, the distributed geometric routing. The thesis consists of two parts dealing with parallel and distributed techniques in geometry. In the first part, two independent problems are considered: (1) we proposed an implementable parallel algorithm for the Euclidean Steiner tree problem; (2) we proposed a Euclidean parallel Voronoi diagram algorithm. In the second part, using computational geometry techniques, we proposed algorithms for two similar problems: (3) we proposed an algorithm to setup a communication links in the emergencies by introducing relay (Steiner) nodes. Also, we present a 2-approximation to assign the transmitting ranges and finally, (4) we proposed a fully distributed algorithm to extract the connected, planar graph for wireless geometric routing. In addition, we presents geometric routing algorithm and established its lower bound. Our results of Steiner trees, Voronoi diagram and geometric routing are for, respectively, the server-client, the hypercube, and the long-distance computational models.
Johnnie Baker, Dr (Advisor)
Feodor Dragan, Dr (Committee Member)
Paul Farrell, Dr (Committee Member)
Mohammad Khan, Dr (Committee Member)
Sprunt Samuel, Dr (Committee Member)
87 p.
Computer Science
Steiner tree; Voronoi diagram; range assignment; geometric routing

Recommended Citations

Citations

  • Muhammad, R. B. (2009). Parallel and Network Algorithms and Applications for Steiner Trees and Voronoi Diagram [Doctoral dissertation, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1259182746

    APA Style (7th edition)

  • Muhammad, Rashid. Parallel and Network Algorithms and Applications for Steiner Trees and Voronoi Diagram. 2009. Kent State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1259182746.

    MLA Style (8th edition)

  • Muhammad, Rashid. "Parallel and Network Algorithms and Applications for Steiner Trees and Voronoi Diagram." Doctoral dissertation, Kent State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=kent1259182746

    Chicago Manual of Style (17th edition)

kent1259182746
1,161
© 2009, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.