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

DSpace/Manakin Repository

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

Show simple item record

dc.contributor.author Ramanujan, M.S.
dc.date.accessioned 2013-10-08T11:00:51Z
dc.date.available 2013-10-08T11:00:51Z
dc.date.issued 2013-10-08T11:00:51Z
dc.date.submitted 2013
dc.identifier.uri http://hdl.handle.net/123456789/342
dc.description.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. en_US
dc.publisher.publisher
dc.subject FPT Algorithms en_US
dc.subject Parameterized Complexity en_US
dc.subject HBNI Th59 en_US
dc.title Parameterized graph separation problems: new techniques and algorithms[HBNI Th59] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Saket Saurabh
dc.description.advisor Venkatesh Raman
dc.description.pages 264p. en_US
dc.type.mainsub Computer Science en_US

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 simple item record

Search DSpace


Advanced Search

Browse

My Account