Minmax sink location problem on dynamic cycle networks

Simple item page
dc.contributor.authorDas, Rajib Chandra
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorBenkoczi, Robert
dc.date.accessioned2019-07-03T18:43:34Z
dc.date.available2019-07-03T18:43:34Z
dc.date.issued2018
dc.degree.levelMastersen_US
dc.description.abstractWe 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.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/5443
dc.language.isoen_USen_US
dc.proquest.subject0984en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectcluster head foresten_US
dc.subjectcycle networksen_US
dc.subjectfeasibility testen_US
dc.subjectminmax objectiveen_US
dc.subjectsink locationen_US
dc.subjectDissertations, Academicen_US
dc.titleMinmax sink location problem on dynamic cycle networksen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Das_Rajib_MSC_2018.pdf
Size:
1.45 MB
Format:
Adobe Portable Document Format
Description:
Masters thesis of Rajib Das, Department of computer science.
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses