Parameterized graph separation problems: new techniques and algorithms[HBNI Th59]

DSpace/Manakin Repository

Parameterized graph separation problems: new techniques and algorithms[HBNI Th59]

Show full item record

Title: Parameterized graph separation problems: new techniques and algorithms[HBNI Th59]
Author: Ramanujan, M.S.
Advisor: Saket Saurabh; Venkatesh Raman
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2013
Pages: 264p.
Abstract: 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.
URI: http://hdl.handle.net/123456789/342

Files in this item

Files Size Format View
HBNI Th59.pdf 1.823Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account