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

DSpace/Manakin Repository

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

Show simple item record

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, 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. en_US
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

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account