Back to search

Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science

Minsum sink location and evacuation problem on dynamic cycle networks

Abstract

dc:description.abstract

In 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 × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/5451

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bashar, Md Khairul; University of Lethbridge. Faculty of Arts and Science. Minsum sink location and evacuation problem on dynamic cycle networks. Masters thesis, Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science, 2018. https://hdl.handle.net/10133/5451