The Kernelization complexity of some domination and covering problems [HBNI Th 44]

DSpace/Manakin Repository

The Kernelization complexity of some domination and covering problems [HBNI Th 44]

Show simple item record

dc.contributor.author Geevarghese Philip
dc.date.accessioned 2012-04-24T10:39:33Z
dc.date.available 2012-04-24T10:39:33Z
dc.date.issued 2012-04-24T10:39:33Z
dc.date.submitted 2011
dc.identifier.uri http://hdl.handle.net/123456789/274
dc.description.abstract Polynomial-time preprocessing is a simple algorithmic strategy which has been widely employed in practice to tackle hard problems. The quantification and analysis of the efficiency of preprocessing algorithms are, in a certain precise sense, outside the pale of classical complexity theory. The notion of kernelization from parameterized complexity theory provides a framework for the mathematical analysis of polynomial-time preprocessing algorithms. Both kernelization and the closely related notion of fixed-parameter tractable (FPT) algorithms are very active areas of current research. In this thesis we describe the results of our study of the kernelization complexity of some graph domination and covering problems. en_US
dc.publisher.publisher
dc.subject Kernelization Complexity en_US
dc.subject HBNI Th 44 en_US
dc.title The Kernelization complexity of some domination and covering problems [HBNI Th 44] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Venkatesh Raman
dc.description.pages 160p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNI Th44 TCS.pdf 1.482Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account