Minmax sink location problem on dynamic cycle networks
Date
2018
Authors
Das, Rajib Chandra
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
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.
Description
Keywords
cluster head forest , cycle networks , feasibility test , minmax objective , sink location , Dissertations, Academic