Back to search

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

Minmax sink location problem on dynamic cycle networks

Abstract

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.

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
  • Das, Rajib Chandra
  • 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/5443

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

Das, Rajib Chandra; University of Lethbridge. Faculty of Arts and Science. Minmax sink location problem on dynamic cycle networks. Masters thesis, Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science, 2018. https://hdl.handle.net/10133/5443