Exact Algorithms for Optimization and parameterized versions of some graph theoretic problems[HBNI Th 6]

Show simple item record

dc.contributor.author Saket Saurabh
dc.date.accessioned 2009-09-17T07:53:47Z
dc.date.available 2009-09-17T07:53:47Z
dc.date.issued 2009-09-17T07:53:47Z
dc.date.submitted 2008
dc.identifier.uri https://dspace.imsc.res.in/xmlui/handle/123456789/119
dc.description.abstract The class of NP-hard combinatorial optimization problems, need to be solved exactly for various applications in theory and practice, brings the need for exact algorithms. Parameterized complexity is an exact algorithmic approach to deal with intractable computational problems having some small parameters. This thesis considers various problems from the exact algorithm paradigm for both parameterized and optimization versions of the problems. The first part of the thesis consists of FPT algorithms for various graph problems and the other part consists of exact algorithms for optimization versions of a few graph problems. It is shown that several problems like dominating set, independent set that are hard for various 'parameterized complexity classes', on general graphs, become fixed parameter tractable on graphs with no small cycles. An FPT algorithm is given for the Directed Maximum Leaf out-Tree problem, which is the problem of finding a directed out-tree, with at least k leaves in directed graphs. Finally W[1]-hardness results is given for variations of coloring problems like LIST coloring and Equitable coloring when parameterized by the treewidth of the input graph. Three techniques are introduced in the second part of the thesis, to design non-trivial exact algorithms and are illustrated with several examples. The first technique obtains a non-trivial exact algorithm for optimization versions of various problems using parameterized algorithms for the same problems. The second technique illustrates the idea of designing exact algorithms by enumerating maximal independent sets (MIS) in a graph. This technique is exemplified by designing the currently fastest polynomial space exact algorithms for ODD Cycle transversal, Minimum maximal matching, Minimum edge dominating Set and Matrix Dominating Set. The last technique is based on different combinations of Branch & Reduce and dynamic programming on graphs of bounded treewidth. It is illustrated by giving the fastest known algorithms for a number of NP hard problems including minimal maximal matching and its variations and counting the number of 3-colorings of a graph. The exact algorithms given for optimization versions of Maximum r-Regular induced subgraph problems. An O(c^n) time algorithms for these problems for any fixed constant r, where c is a positive constant, strictly less than 2, depending on r alone. en_US
dc.subject Optimization Algorithms en_US
dc.subject Graph Theory en_US
dc.title Exact Algorithms for Optimization and parameterized versions of some graph theoretic problems[HBNI Th 6] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Raman, Venkatesh
dc.description.pages vii; 264p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account