Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
Minsum sink location and evacuation problem on dynamic cycle networks
Abstract
dc:description.abstractIn this thesis, we study 1-sink location and k-sink evacuation problem on dynamic cycle networks. We consider the 1-sink location problem is to find the optimal location of the 1 sink, while the k-sink evacuation problem is to find the optimal evacuation protocol for the given locations of the k sinks. Both results minimize the sum of the evacuation times of all the supply located at the vertices to the sink/s of a given cycle network of n vertices. We present an efficient algorithm with a useful data structure that finds the optimal location of the 1 sink in O(n) time when the capacity of the edges are uniform. If the edges have arbitrary capacities, we solve the problem in O(nlogn)$ time by an extension of the data structure. We also propose an O(n) time algorithm to solve the k-sink evacuation problem with uniform edge capacity.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Grantor dc:publisher
- Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Bashar, Md Khairul
- University of Lethbridge. Faculty of Arts and Science
- Advisor dc:contributor.supervisor
-
- Benkoczi, Robert
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/5451