2026-09-20T05:26:01.266308700Zhttps://opus.uleth.ca/server/oai/request

oai:opus.uleth.ca:10133/32352019-02-07T06:09:06Zcom_10133_3346com_10133_1com_10133_296col_10133_3347col_10133_298

Gaur, Daya Benkoczi, Robert Sabbir, Tarikul Alam Khan 2013-01-18T18:26:14Z 2013-01-18T18:26:14Z 2011 https://hdl.handle.net/10133/3235 ix, 89 leaves : ill. ; 29 cm Solving NP-hard facility location problems in wireless network planning is a common scenario. In our research, we study the Covering problem, a well known facility location problem with applications in wireless network deployment. We focus on networks with a sparse structure. First, we analyzed two heuristics of building Tree Decomposition based on vertex separator and perfect elimination order. We extended the vertex separator heuristic to improve its time performance. Second, we propose a dynamic programming algorithm based on the Tree Decomposition to solve the Covering problem optimally on the network. We developed several heuristic techniques to speed up the algorithm. Experiment results show that one variant of the dynamic programming algorithm surpasses the performance of the state of the art mathematical optimization commercial software on several occasions. en_US Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011 Arts and Science Department of Mathematics and Computer Science Thesis (University of Lethbridge. Faculty of Arts and Science) Combinatorial optimization Trees (Graph theory) Algorithms Wireless internet Wireless sensor networks Dissertations, Academic Topology sensitive algorithms for large scale uncapacitated covering problem Thesis Masters open.access