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

DSpace/Manakin Repository

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

Show full item record

Title: Parameterized Complexity of Graph Partitioning and Geometric Covering[HBNI Th115]
Author: Sudheshna Kolay
Advisor: Saket Saurabh
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2016
Pages: 231p.
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.
URI: http://hdl.handle.net/123456789/402

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 full item record

Search DSpace


Advanced Search

Browse

My Account