Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

On online and approximate cover time problems

Basit öğe kaydını göster

dc.contributor Graduate Program in Mathematics.
dc.contributor.advisor Işlak, Ümit.
dc.contributor.author Yıldız, Mehmet Akif.
dc.date.accessioned 2023-03-16T11:21:48Z
dc.date.available 2023-03-16T11:21:48Z
dc.date.issued 2020.
dc.identifier.other MATH 2020 Y56
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/15318
dc.description.abstract As a generalization of the classical coupon collector problem in the probability theory, the cover time in random walks on Markov chains has been investigated in numerous studies in the literature. Especially, there are several results for the cover time of a simple random walk on connected and undirected graphs. In this thesis, we study two new problems about the cover time of graphs. Firstly, we build an on-line model where there is a walker moving with random time intervals on a graph growing in time. We initiate this study by examining the number of vertices covered up to a fixed time for a simple model, and we discuss further research directions. Secondly, we generalize the classical cover time definition in order to understand the differences between the partial covering and the full covering. We initiate this study with the investigation of the approximate covering time on specific graph families such as path graphs and complete graphs, and our main motivation is to explore the structure of the graphs allowing easy partial covering in terms of the order of magnitude. For the sake of completeness, we also give some preliminary results about the classical cover time problem and several variations of the problem from the literature such as edge covering and dynamic versions in the thesis.
dc.format.extent 30 cm.
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020.
dc.subject.lcsh Probability measures.
dc.title On online and approximate cover time problems
dc.format.pages x, 74 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım