Kernels for the F-Deletion Problem (Record no. 48829)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02170nam a2200265Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2012||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th 41 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Neeldhara Misra |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Kernels for the F-Deletion Problem |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2012 |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2012 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | F-Deletion Problem |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Kernelization |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Parameterized Complexity |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Tree Decompositions |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Tree Width |
| 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/328 |
| 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 Th 41 | 67085 | http://www.imsc.res.in/xmlui/handle/123456789/328 | THESIS & DISSERTATION |