Parametric duality and kernelization: Lower bounds and upper bounds on kernel size | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/25201

Title: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size
Author/Creator: Chen, J. N.; Fernau, Henning; Kanj, I. A.; Xia, G.
Description: We develop new techniques to derive lower bounds on the kernel size for certain parameterized problems. For example, we show that unless P = NP, PLANAR VERTEX COVER does not have a problem kernel of size smaller than 4k/3, and PLANAR INDEPENDENT SET and PLANAR DOMINATING SET do not have kernels of size smaller than 2k. We derive an upper bound of 67k on the problem kernel for PLANAR DOMINATING SET improving the previous 335k upper bound by Alber et al.
Relation: STACS 2005 22nd Annual Symposium on Theoretical Aspects of Computer Science Stuttgart, Germany, February 24-26, 2005. Proceedings. (Stuttgart, Germany February 24-26, 2005)
Date: 2005
Publisher: Springer Verlag
Keyword(s): kernelization; parameterized complexity
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/25201
Identifier: ISBN:3-540-24998-2
Language: eng

12 Visitors

13 Hits

NOVA. The University of Newcastle's Digital Repository