000			02072nam a2200265Ia 4500
008			160627s2013||||xx |||||||||||||| ||und||
080			_aHBNI Th59
100			_aRamanujan, M.S. _eauthor
245			_aParameterized graph separation problems: new techniques and algorithms
260			_c2013
300			_a264p.
502			_a2013
502			_bPh.D
502			_cHBNI
520	3		_aMenger'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	1	4	_aComputer Science
653	1	0	_aFPT Algorithms
653	1	0	_aHBNI Th59
653	1	0	_aParameterized Complexity
720	1		_aSaket Saurabh _eThesis advisor [ths]
720	1		_aVenkatesh Raman _eThesis advisor [ths]
856			_uhttp://www.imsc.res.in/xmlui/handle/123456789/342
942			_2THESIS175 _cTHESIS
999			_c48880 _d48880