Show simple item record

dc.contributor.supervisor Benkoczi, Robert
dc.contributor.author Das, Rajib Chandra
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2019-07-03T18:43:34Z
dc.date.available 2019-07-03T18:43:34Z
dc.date.issued 2018
dc.identifier.uri https://hdl.handle.net/10133/5443
dc.description.abstract We address both 1 and k sink location problems on dynamic cycle networks. Our 1-sink algorithms run in O(n) and O(nlogn) time for uniform and general edge capacity cases, respectively. We improve the previously best known O(nlogn) time algorithm for single sink introduced by Xu et al. [Xu et al. 2015] with uniform capacities. When k¿1, we improve two results [Benkoczi et al. 2017] for both with uniform and arbitrary capacities by a factor of O(logn). Using the same sorted matrices optimization framework originally devised by Frederickson and Johnson and employed by [Benkoczi et al. 2017], our algorithms for the k-sink problems have time complexities of O(nlogn) for uniform, and O(nlog3 n) for arbitrary capacities. Key to our results is a novel data structure called a cluster head forest, which allows one to compute batches of queries for evacuation time efficiently. en_US
dc.language.iso en_US en_US
dc.publisher Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science en_US
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US
dc.subject cluster head forest en_US
dc.subject cycle networks en_US
dc.subject feasibility test en_US
dc.subject minmax objective en_US
dc.subject sink location en_US
dc.subject Dissertations, Academic en_US
dc.title Minmax sink location problem on dynamic cycle networks en_US
dc.type Thesis en_US
dc.publisher.faculty Arts and Science en_US
dc.publisher.department Department of Mathematics and Computer Science en_US
dc.degree.level Masters en_US
dc.proquest.subject 0984 en_US
dc.proquestyes Yes en_US
dc.embargo No en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record