Algorithms for Parameterized Constraint Satisfaction Problems. / Crowston, Robert.

2013. 125 p.

Research output: ThesisDoctoral Thesis

Unpublished

Documents

Abstract

There are many problems requiring superpolynomial time in the size of the instance. Parameterized complexity considers the problem having an additional parameter, isolating the superpolynomial behaviour. A problem is fixed-parameter tractable if it has an algorithm which has running time polynomial in the size of the instance multiplied by a (usually superpolynomial) function of the parameter.

This thesis considers the parameterized complexity of several problems where the aim is to satisfy a set of constraints. For such problems, it is known that a certain proportion of constraints can be satisfied. We consider the parameterized complexity of such problems with respect to the number of constraints satisfied above this, as well as with respect to other structural parameters.
Original languageEnglish
QualificationPh.D.
Awarding Institution
Publication statusUnpublished - 2013
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 17299067