The Kernelization complexity of some domination and covering problems
Material type:
TextPublication details: 2011Description: 160pSubject(s): Computer Science | HBNI Th 44 | Kernelization ComplexityOnline resources: Click here to access online Dissertation note: 2011Ph.DHBNI Abstract: Polynomial-time preprocessing is a simple algorithmic strategy which has been widely employed in practice to tackle hard problems. The quantification 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.
THESIS & DISSERTATION
| Current library | Home library | Call number | Materials specified | URL | Status | Date due | Barcode |
|---|---|---|---|---|---|---|---|
| IMSc Library | IMSc Library | HBNI Th44 (Browse shelf (Opens below)) | Link to resource | Available | 67234 |
Browsing IMSc Library shelves Close shelf browser (Hides shelf browser)
2011
Ph.D
HBNI
Polynomial-time preprocessing is a simple algorithmic strategy which has been widely employed in practice to tackle hard problems. The quantification 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.
There are no comments on this title.