# Parameterized Complexity of Graph Partitioning and Geometric Covering[HBNI Th115]

 dc.contributor.author Sudheshna Kolay dc.date.accessioned 2017-05-16T10:03:02Z dc.date.available 2017-05-16T10:03:02Z dc.date.issued 2017-05-16T10:03:02Z dc.date.submitted 2016 dc.identifier.uri http://hdl.handle.net/123456789/402 dc.description.abstract In this thesis, we consider problems in graph partitioning and geometric covering in the realm of Parameterized complexity. Several algorithmic paradigms have been developed in order to cope with the hard problems of classical complexity. However, any algorithmic paradigm meant to cope with the hard problems and to run in polynomial time, such as approximation algorithms or randomized algorithms, must give in to inaccuracy. Parameterized complexity is a fairly new branch of theoretical computer science, with yet another measure of efficiency in terms of running time but where there in no compromise on accuracy. A parameterized problem associates with each input instance, of a classical problem, en_US a parameter, which is usually a positive integer. The aim is to contain the exponential explosion in the running time of algorithms such that the dependence of the exponential function in the running time is only on the parameter associated with the input instance. When carefully chosen, the parameter tends to be much smaller than the input instance. Therefore, we expect parameterized problems to have more efficient algorithms, in terms of running time, than their counterparts in the classical complexity setting. dc.subject Parameterized Algorithms en_US dc.subject Graph Partitioning en_US dc.subject Geometric Covering en_US dc.subject Covering Problems en_US dc.subject HBNI Th115 en_US dc.title Parameterized Complexity of Graph Partitioning and Geometric Covering[HBNI Th115] en_US dc.type.degree Ph.D en_US dc.type.institution HBNI en_US dc.description.advisor Saket Saurabh dc.description.pages 231p. en_US dc.type.mainsub Computer Science en_US

## Files in this item

Files Size Format View
HBNI Th115.pdf 1.583Mb PDF View/Open