Kernels for the F-Deletion Problem[HBNI Th 41]

DSpace/Manakin Repository

Kernels for the F-Deletion Problem[HBNI Th 41]

Show simple item record Neeldhara Misra 2012-08-21T06:20:19Z 2012-08-21T06:20:19Z 2012-08-21T06:20:19Z 2012
dc.description.abstract In this thesis, the parameterized framework is used for the design and analysis of algorithms for NP-complete problems. This amounts to studying the parameterized version of the classical decision version. Herein, the classical language appended with a secondary measure called a “parameter”. The central notion in parameterized complexity is that of fixed-parameter tractability, which means given an instance (x, k) of a parameterized language L, deciding whether (x, k) an element of L in time f(k) ·p(|x|), where f is an arbitrary function of k alone and p is a polynomial function. The notion of kernelization formalizes preprocessing or data reduction, and refers to polynomial time algorithms that transform any given input into an equivalent instance whose size is bounded as a function of the parameter alone. The center of attention in this thesis is the F-Deletion problem, a vastly general question that encompasses many fundamental optimization problems as special cases. In particular, provide evidence supporting a conjecture about the kernelization complexity of the problem, and this work branches off in a number of directions, leading to results of independent interest. This thesis also studies the Colorful Motifs problem, a well-known question that arises frequently in practice. Our investigation demonstrates the hardness of the problem even when restricted to very simple graph classes. en_US
dc.subject Kernelization en_US
dc.subject Tree Decompositions en_US
dc.subject Tree Width en_US
dc.subject F-Deletion Problem en_US
dc.subject Parameterized Complexity en_US
dc.title Kernels for the F-Deletion Problem[HBNI Th 41] en_US Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Venkatesh Raman
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNI Th41.pdf 4.914Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account