Exact Algorithms for Optimization and parameterized versions of some graph theoretic problems (Record no. 48808)
[ view plain ]
000 -LEADER | |
---|---|
fixed length control field | 03083nam a2200229Ia 4500 |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
fixed length control field | 160627s2008||||xx |||||||||||||| ||und|| |
100 ## - MAIN ENTRY--AUTHOR NAME | |
Personal name | Saket Saurabh |
Relator term | author |
245 ## - TITLE STATEMENT | |
Title | Exact Algorithms for Optimization and parameterized versions of some graph theoretic problems |
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
Year of publication | 2008 |
300 ## - PHYSICAL DESCRIPTION | |
Number of Pages | vii; 264p. |
502 ## - DISSERTATION NOTE | |
Dissertation note | 2008 |
502 ## - DISSERTATION NOTE | |
Degree Type | Ph.D |
502 ## - DISSERTATION NOTE | |
Name of granting institution | HBNI |
520 3# - SUMMARY, ETC. | |
Summary, etc | 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. |
650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical Term | Computer Science |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Graph Theory |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Optimization Algorithms |
720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
Thesis Advisor | Raman, Venkatesh |
Relator term | Thesis advisor [ths] |
856 ## - ELECTRONIC LOCATION AND ACCESS | |
Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/119 |
942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
Koha item type | THESIS & DISSERTATION |
Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
---|---|---|---|---|---|---|---|---|
IMSc Library | HBNI Th6 | 61362 | http://www.imsc.res.in/xmlui/handle/123456789/119 | THESIS & DISSERTATION |