The Kernelization complexity of some domination and covering problems (Record no. 48840)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 01365nam a2200229Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2011||||xx |||||||||||||| ||und|| |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Geevarghese Philip |
| Relator term | author |
| 245 #4 - TITLE STATEMENT | |
| Title | The Kernelization complexity of some domination and covering problems |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2011 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 160p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2011 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th 44 |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Kernelization Complexity |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Venkatesh Raman |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/274 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | HBNI Th44 | 67234 | http://www.imsc.res.in/xmlui/handle/123456789/274 | THESIS & DISSERTATION |