Please use this identifier to cite or link to this item:

`http://hdl.handle.net/10603/4711`

Title: | The Kernelization complexity of some domination and covering problems |

Researcher: | Geevarghese, Philip |

Guide(s): | Venkatesh, Raman |

Keywords: | Graph Domination Kernelization complexity |

Upload Date: | 17-Sep-2012 |

University: | Homi Bhabha National Institute |

Completed Date: | September, 2011 |

Abstract: | In graph domination problem the input is a graph, and the question is whether there exists a subgraph which ?dominates? the rest of the graph. For example, in the archetypal Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there exists a set S of at most k vertices of G such that there is an edge in the graph from every vertex not in S to some vertex in S ? such a set S is called a dominating set of the graph. Other graph domination problems either put different constraints on the subgraph, or define the notion of domination differently, or both. In a graph covering problem the input is again a graph, and the question is whether there exists a subgraph whose removal from the graph results in a ?simple? graph. For example, in the classical Vertex Cover problem the input consists of a graph G and a positive integer k, and the question is whether there exists a set S of at most k vertices of G such that removing S from G leaves a graph with no edges. Other graph covering problems either put different constraints on the subgraph, or define the notion of simplicity differently, or both. We investigate the kernelization complexity of some NP-hard domination and covering problems. Very briefly, the idea is to associate a parameter ? a positive integer which may be expected to be small for large classes of inputs ? with each input instance. The problem now is to see if we can compress the instance in polynomial time to an equivalent instance whose size is a small function of the parameter, in polynomial time. Compressing the input to a small size then enables us to apply other methods on the small instance to solve the original problem in feasible time.In this Thesis we obtain various upper and lower bounds on the kernelization complexity of the following graph domination and covering problems. In each case, the parameter is the size of the solution being sought: Dominating Set, Connected Dominating Set, Pathwidth-One Vertex Deletion. |

Pagination: | 203p. |

URI: | http://hdl.handle.net/10603/4711 |

Appears in Departments: | Department of Mathematical Sciences |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

01_title.pdf | Attached File | 207.69 kB | Adobe PDF | View/Open |

02_certificate.pdf | 81.01 kB | Adobe PDF | View/Open | |

03_declaration.pdf | 75.76 kB | Adobe PDF | View/Open | |

04_dedication.pdf | 45.01 kB | Adobe PDF | View/Open | |

05_acknowledgements.pdf | 110.76 kB | Adobe PDF | View/Open | |

06_contents.pdf | 114.55 kB | Adobe PDF | View/Open | |

07_synopsis.pdf | 129.71 kB | Adobe PDF | View/Open | |

08_list of figures.pdf | 60.16 kB | Adobe PDF | View/Open | |

09_list of tables.pdf | 52.89 kB | Adobe PDF | View/Open | |

10_part 1.pdf | 247.1 kB | Adobe PDF | View/Open | |

11_part 2.pdf | 568.52 kB | Adobe PDF | View/Open | |

12_part 3.pdf | 519.66 kB | Adobe PDF | View/Open | |

13_part 4.pdf | 179.77 kB | Adobe PDF | View/Open | |

14_references.pdf | 163 kB | Adobe PDF | View/Open | |

15_abstract.pdf | 46.7 kB | Adobe PDF | View/Open | |

16_summary.pdf | 103.29 kB | Adobe PDF | View/Open |

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.