Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8943
Title: Exact Exponential Algorithms to solve NP-Hard Problems
Authors: MAITY, SOUMEN
DARSAN, T I
Dept. of Mathematics
20191172
Keywords: Algorithms
Graph Theory
Exact Exponential
Issue Date: May-2024
Citation: 47
Abstract: The first part of the thesis is mainly a literature study of the book, ”Exact Exponential Algorithms” by Fomin and Krastch. We explain different techniques to solve computational problems through exact algorithms. The techniques are branching, dynamic programming and measure and conquer and also treewidth. These are explained using examples and di↵erent algorithms. In the second part of the thesis, we introduce the problem, Component order connectivity using some examples and ILP formulation. We also introduce it’s edge version, component order edge connectivity and parameterized version and give some results. Then we give algorithms to find the solution when the instance is tree or a bounded degree graph.
URI: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/8943
Appears in Collections:MS THESES

Files in This Item:
File Description SizeFormat 
20191172_T_I_Darsan_MS_ThesisMS Thesis714.26 kBAdobe PDFView/Open    Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.