On online and approximate cover time problems

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.