Dynamic Programming using Representative Families [HBNI Th87]

DSpace/Manakin Repository

Dynamic Programming using Representative Families [HBNI Th87]

Show simple item record

dc.contributor.author Fahad, P
dc.date.accessioned 2015-12-31T12:04:51Z
dc.date.available 2015-12-31T12:04:51Z
dc.date.issued 2015-12-31T12:04:51Z
dc.date.submitted 2015
dc.identifier.uri http://hdl.handle.net/123456789/372
dc.description.abstract This thesis studies algorithms mainly in the parameterized complexity framework. The thesis has three conceptual parts, (i) efficient computation of representative families, and its application in FPT and exact algorithms, (ii) study of Matroid Girth and Matroid Connectivity problems under various natural parameters and (iii) single exponential polynomial space FPT algorithm for Steiner Tree parameterized by the number of terminals. Let S be a family of p sized sets over a universe U. A subfamily S' of S is called a q-representative family of S, if S' satisfies the following condition: for any q sized subset Y of U, if there is a set S_1 in S which is disjoint from Y, then there is a set S_1' in S' which is disjoint from Y. The definition of representative family can be extended to matroids. We give efficient computation of representative family both for set systems and matroids. It is demonstrated that, how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include fastest known parameterized (and exact) algorithms for Long Directed Cycle, Minimum Equivalent Graph, "connectivity" problems such as Steiner Tree on graphs of treewidth at most t and Multilinear Monomial Testing. These methods are also used to resolve parameterized complexity of graph editing problems. Matroid Girth and Matroid Connectivity problems are studied on linear matroids representable over a field F_q in the parameterized complexity framework. The following parameters are considered; (i) solution size, k, (ii) rank(M), and (iii) rank(M) + q, where M is the input matroid. It is shown that these problems are unlikely to be in FPT when parameterized by k or rank(M). Fast FPT algorithm is given for these problems when parameterized by rank(M) + q. Another problem considered in this thesis is weighted Steiner Tree problem parameterized by the number of terminals and gives the first single-exponential time, polynomial-space FPT algorithm for the problem. en_US
dc.subject Dynamic Programming en_US
dc.subject Representative Families en_US
dc.subject Algorithms en_US
dc.subject Parameterized Complexity en_US
dc.subject HBNI Th87 en_US
dc.title Dynamic Programming using Representative Families [HBNI Th87] 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 278p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNI Th87.pdf 1.791Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account