[图书][B] Fundamentals of parameterized complexity
RG Downey, MR Fellows - 2013 - Springer
Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …
algorithm design and analysis, with a broad range of theoretical and practical aspects that …
[图书][B] Parameterized complexity
RG Downey, MR Fellows - 2012 - books.google.com
The idea for this book was conceived over the second bottle of Villa Maria's Caber net
Medot'89, at the dinner of the Australasian Combinatorics Conference held at Palmerston …
Medot'89, at the dinner of the Australasian Combinatorics Conference held at Palmerston …
Texts in Theoretical Computer Science An EATCS Series
ACDHJ Hartmanis, T Henzinger, JHNJT Leighton… - 2006 - Springer
Classical complexity theory analyzes and classifies problems by the amount of a resource,
usually time or space, that is required by algorithms solving them. It was a fundamental idea …
usually time or space, that is required by algorithms solving them. It was a fundamental idea …
On problems without polynomial kernels
Kernelization is a strong and widely-applied technique in parameterized complexity. A
kernelization algorithm, or simply a kernel, is a polynomial-time transformation that …
kernelization algorithm, or simply a kernel, is a polynomial-time transformation that …
On the efficiency of polynomial time approximation schemes
M Cesati, L Trevisan - Information Processing Letters, 1997 - Elsevier
A polynomial time approximation scheme (PTAS) for an optimization problem A is an
algorithm that given in input an instance of A and ε> 0 finds a (1+ ε)-approximate solution in …
algorithm that given in input an instance of A and ε> 0 finds a (1+ ε)-approximate solution in …
[PDF][PDF] Parameterized algorithmics: A graph-theoretic approach
H Fernau - 2005 - Citeseer
Parameterized Algorithmics: A Graph-Theoretic Approach Page 1 Parameterized Algorithmics:
A Graph-Theoretic Approach Henning Fernau Universität Tübingen, WSI für Informatik, Sand …
A Graph-Theoretic Approach Henning Fernau Universität Tübingen, WSI für Informatik, Sand …
On parameterized approximability
LNCS 4169 - On Parameterized Approximability Page 1 On Parameterized Approximability
Yijia Chen1, Martin Grohe2, and Magdalena Grüber2 1 BASICS, Department of Computer …
Yijia Chen1, Martin Grohe2, and Magdalena Grüber2 1 BASICS, Department of Computer …
On problems without polynomial kernels
Kernelization is a central technique used in parameterized algorithms, and in other
approaches for coping with NP-hard problems. In this paper, we introduce a new method …
approaches for coping with NP-hard problems. In this paper, we introduce a new method …
The Turing way to parameterized complexity
M Cesati - Journal of Computer and System Sciences, 2003 - Elsevier
We propose a general proof technique based on the Turing machine halting problem that
allows us to establish membership results for the classes W [1], W [2], and W [P]. Using this …
allows us to establish membership results for the classes W [1], W [2], and W [P]. Using this …
Computability and Complexity
R Downey - 1997 - Springer
One of the great achievements of humanity has been the clarification of the concept of an
algorithmic process. Having done this, we then sought to understand the structure of …
algorithmic process. Having done this, we then sought to understand the structure of …