NP-Hardness is a well-known theory to identify the hardness of computational problems.
It is believed that NP-Hard problems are unlikely to admit polynomial-time algorithms.
However since many NP-Hard problems are of practical significance, different approaches
are proposed to solve them: Approximation algorithms, randomized algorithms and heuristic
algorithms. None of the approaches meet the practical needs. Recently parameterized
computation and complexity has attracted a lot of attention and been a fruitful branch of
the study of efficient algorithms. By taking advantage of the moderate value of parameters
in many practical instances, we can design efficient algorithms for the NP-Hard problems in
practice.
In this dissertation, we discuss a new approach to design efficient parameterized algorithms,
kernelization. The motivation is that instances of small size are easier to solve.
Roughly speaking, kernelization is a preprocess on the input instances and is able to significantly reduce their sizes.
We present a 2k kernel for the cluster editing problem, which improves the previous
best kernel of size 4k; We also present a linear kernel of size 7k 2d for the d-cluster
editing problem, which is the first linear kernel for the problem. The kernelization algorithm
is simple and easy to implement.
We propose a quadratic kernel for the pseudo-achromatic number problem. This
implies that the problem is tractable in term of parameterized complexity. We also study
the general problem, the vertex grouping problem and prove it is intractable in term of
parameterized complexity.
In practice, many problems seek a set of good solutions instead of a good solution.
Motivated by this, we present the framework to study enumerability in term of parameterized
complexity. We study three popular techniques for the design of parameterized algorithms,
and show that combining with effective enumeration techniques, they could be transferred
to design efficient enumeration algorithms.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2010-05-7845 |
| Date | 2010 May 1900 |
| Creators | Meng, Jie |
| Contributors | Chen, Jianer, Friesen, Donald K. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | thesis, text |
| Format | application/pdf |
Page generated in 0.0028 seconds