Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/2945| Title: | Lossy Kernels for Few Graph Contraction ProbleMS |
| Authors: | MAITY, SOUMEN Saurabh, Saket GUNDA, SPOORTHY Dept. of Mathematics 20141111 |
| Keywords: | 2019 Lossy Kernels Graph Contraction |
| Issue Date: | Apr-2019 |
| Abstract: | We study a few graph contraction problems Chordal Contraction, Clique Contraction and Split Contraction, from the viewpoint of Lossy Kernelization, which is a recently introduced framework to study NP-hard problems. H-Contraction problem is to find set of edges such that when contracted will give the graph H. We study approximate kernel for the minimization version of these problems by including some parameters. |
| URI: | http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/2945 |
| Appears in Collections: | MS THESES |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Final_Thesis_spoorthy.pdf | 1.27 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.