{"id":{"repo_id":"lethbridge","oai_identifier":"oai:opus.uleth.ca:10133/3235"},"canonical_url":"https://search.dev.ndltd.org/etd/lethbridge/oai:opus.uleth.ca:10133/3235","repository":{"repo_id":"lethbridge","name":"University of Lethbridge","base_url":"https://opus.uleth.ca/server/oai/request"},"display":{"title":"Topology sensitive algorithms for large scale uncapacitated covering problem","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sabbir, Tarikul Alam Khan"],"institution":"Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Gaur, Daya","Benkoczi, Robert"],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011","date_published":"2011","updated_at":"2026-08-21T16:45:58Z","subjects":["Combinatorial optimization","Trees (Graph theory)","Algorithms","Wireless internet","Wireless sensor networks","Dissertations, Academic"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10133/3235"],"render_values":[{"text":"hdl:10133/3235","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10133/3235","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"source_record":{"url":"https://opus.uleth.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopus.uleth.ca%3A10133%2F3235","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.supervisor","label":"Supervisor","values":["Gaur, Daya","Benkoczi, Robert"]},{"key":"dc:creator","label":"Author","values":["Sabbir, Tarikul Alam Khan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-01-18T18:26:14Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-01-18T18:26:14Z"]},{"key":"dc:date.issued","label":"Date","values":["2011"]},{"key":"dc:publisher","label":"Institution","values":["Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Mathematics and Computer Science"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial optimization","Trees (Graph theory)","Algorithms","Wireless internet","Wireless sensor networks","Dissertations, Academic"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10133/3235"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10133/3235"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["ix, 89 leaves : ill. ; 29 cm"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.other","label":"Dc Description Other","values":["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."]},{"key":"dc:title","label":"Title","values":["Topology sensitive algorithms for large scale uncapacitated covering problem"]}]}],"canonical_facts":{"dc:contributor.supervisor":["Gaur, Daya","Benkoczi, Robert"],"dc:creator":["Sabbir, Tarikul Alam Khan"],"dc:date.accessioned":["2013-01-18T18:26:14Z"],"dc:date.available":["2013-01-18T18:26:14Z"],"dc:date.issued":["2011"],"dc:description":["ix, 89 leaves : ill. ; 29 cm"],"dc:description.abstract":["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."],"dc:description.other":["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."],"dc:identifier":["hdl:10133/3235"],"dc:identifier.uri":["https://hdl.handle.net/10133/3235"],"dc:language.iso":["en_US"],"dc:publisher":["Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011"],"dc:publisher.department":["Department of Mathematics and Computer Science"],"dc:subject":["Combinatorial optimization","Trees (Graph theory)","Algorithms","Wireless internet","Wireless sensor networks","Dissertations, Academic"],"dc:title":["Topology sensitive algorithms for large scale uncapacitated covering problem"],"dc:type":["Thesis"]},"updated_at":"2026-08-21T16:45:58Z"}