Data reduction for connected dominating set

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Imani, Navid
Computationally difficult problems are ubiquitous. Although, sometimes approximations come in handy, accuracy is often a must and hence complexity of optimization seems unavoidable. The classical viewpoint to the complexity considers the instant size as the only factor for computing its hardness, but while dealing with hard problems, many input instances consist of easy parts and other parts that form the hard core of the problem. Therefore, it seems reasonable that before starting a cost-intensive algorithm, a polynomial-time preprocessing phase is executed in order to shrink the instance to the hard core kernel. In fixed-parameter algorithms, this is known as data reduction to a problem kernel. In this thesis, we study data reduction for the connected dominating set problem. In particular, we introduce a set of data reduction rules for the connected dominating set problem and prove that the problem admits a linear-size kernel in planar graphs.
Copyright statement
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact
Scholarly level
Member of collection
Attachment Size
etd4068.pdf 1.41 MB