Show simple item record

dc.contributor.advisorChen, Jianer
dc.creatorXia, Ge
dc.date.accessioned2006-10-30T23:29:36Z
dc.date.available2006-10-30T23:29:36Z
dc.date.created2005-08
dc.date.issued2006-10-30
dc.identifier.urihttp://hdl.handle.net/1969.1/4322
dc.description.abstractMany problems of practical significance are known to be NP-hard, and hence, are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized computation and complexity have been receiving a lot of attention. By taking advantage of small or moderate parameter values, parameterized algorithms provide new venues for practically solving problems that are theoretically intractable. In this dissertation, we design efficient parameterized algorithms for several wellknown NP-hard problems and prove strong lower bounds for some others. In doing so, we place emphasis on the development of new techniques that take advantage of the structural properties of the problems. We present a simple parameterized algorithm for Vertex Cover that uses polynomial space and runs in time O(1.2738k + kn). It improves both the previous O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and Grandoni. This algorithm stands out for both its performance and its simplicity. Essential to the design of this algorithm are several new techniques that use structural information of the underlying graph to bound the search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an “almost-global” analysis of the search tree. We also show that an important structural property of the underlying graphs – the graph genus – largely dictates the computational complexity of some important graph problems including Vertex Cover, Independent Set and Dominating Set. We present a set of new techniques that allows us to prove almost tight computational lower bounds for some NP-hard problems, such as Clique, Dominating Set, Hitting Set, Set Cover, and Independent Set. The techniques are further extended to derive computational lower bounds on polynomial time approximation schemes for certain NP-hard problems. Our results illustrate a new approach to proving strong computational lower bounds for some NP-hard problems under reasonable conditions.en
dc.format.extent1126964 bytesen
dc.format.mediumelectronicen
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherTexas A&M University
dc.subjectAlgorithmsen
dc.subjectComputational Complexityen
dc.subjectComputational Lower Boundsen
dc.subjectParameterized Computationen
dc.titleParameterized algorithms and computational lower bounds: a structural approachen
dc.typeBooken
dc.typeThesisen
thesis.degree.departmentComputer Scienceen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorTexas A&M Universityen
thesis.degree.nameDoctor of Philosophyen
thesis.degree.levelDoctoralen
dc.contributor.committeeMemberFriesen, Donald K.
dc.contributor.committeeMemberWelch, Jennifer L.
dc.contributor.committeeMemberYan, Catherine H.
dc.type.genreElectronic Dissertationen
dc.type.materialtexten
dc.format.digitalOriginborn digitalen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record