Parameterized Enumeration of Neighbour Strings and Kemeny Aggregations
Narges Simjour · UWSpace (University of Waterloo) · 2013
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii In this thesis, we consider approaches to enumeration problems in the parameterized complexity setting. We obtain competitive parameterized algorithms to enumerate all, as well as several of, the solutions for two related problems Neighbour String and Kemeny Rank Aggregation. In both problems, the goal is to find a solution that is as close as possible to a set of inputs (strings and total orders, respectively) according to some distance measure. We also introduce a notion of enumerative kernels for which there is a bijection between solutions to the original instance and solutions to the kernel, and provide such a kernel for Kemeny Rank Aggregation, improving a previous kernel for the problem. We demonstrate how several of the algorithms and notions discussed in this thesis are extensible to a group of parameterized problems, improving published results for some other problems. iii Acknowledgements I would like to thank my supervisor, Professor Naomi Nishimura, for her generous sup-port and invaluable advice on my research. I would also like to thank Professor Jonathan Buss and Professor Timothy Chan for their helpful comments on the direction of my re-search. I wish to thank Professor Bin Ma for fruitful discussions on some of the results in this work. I am also grateful to my thesis committee for spending their valuable time reading this thesis, and for their suggestions which improved the content and presentation of my work. Special thanks to my family for their encouragement and love, and to the many friends I met in Waterloo, for making my PhD experience really enjoyable. iv