Parameterized graph separation problems: new techniques and algorithms (Record no. 48880)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02072nam a2200265Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2013||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th59 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Ramanujan, M.S. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Parameterized graph separation problems: new techniques and algorithms |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2013 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 264p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2013 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | Menger's theorem, which states that the minimum number of vertices whose removal disconnects two vertices s and t in a graph is equal to the maximum number of pairwise vertex disjoint paths from s to t in the graph, is an extremely fundamental theorem in combinatorial optimization and it is known that the minimum s-t cut can be computed in polynomial time. Generalizations of the problem of finding the minimum set of vertices disconnecting two vertices in graph, are called graph separation problems. The main problems the author studies in this thesis are such graph separation problems. The fact that very natural generalizations of the s-t cut problem turn out to be NP-complete has motivated the study of these problems in the framework of Parameterized Complexity and the study of these problems has even emerged as an extremely active and independent subfield over the last few years. This thesis results to design new techniques and frameworks to obtain new as well as improved FPT algorithms for certain kinds of parameterized graph separation problems; resent problems which not graph separation problems themselves, but have some variant of graph separation at their core, after which by using new frameworks as well as existing ones, the author gives new as well as improved FPT algorithms. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | FPT Algorithms |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th59 |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Parameterized Complexity |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Saket Saurabh |
| Relator term | Thesis advisor [ths] |
| 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/342 |
| 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 Th59 | 69366 | http://www.imsc.res.in/xmlui/handle/123456789/342 | THESIS & DISSERTATION |