Data reduction for connected dominating set

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2008
Authors/Contributors
Author: Imani, Navid
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
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 summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd4068.pdf 1.41 MB