Invitation to fixed-parameter algorithms

By Dimitrios M. Thilikos. Computer Science Review, 2007

1,042 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/0df4dab6e3e3df13e478a97176867acbf873621d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

(Meta) Kernelization (2009, background): “2012], as well as books [Cygan et al. 2015; Downey and Fellows 2013; Flum and Grohe 2006; Niedermeier 2006] for a detailed treatment of the area of kernelization.”
Parameterized Complexity of Small Decision Tree Learning (2021, methodology): “In this paper, we investigate the problem of ﬁnding small decision trees (w.r.t. size or depth) under the framework of Parameterized Complexity (Downey and Fellows 2013; Got-tlob, Scarcello, and Sideri 2002; Niedermeier 2006).”
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth (2013, methodology): “See [14,20] for sample applications to the Independent Set / Vertex Cover problems.”
Design and Analysis of Algorithms (2009, methodology): “3 Enabling preemptions affects all the jobs of the instance, thus causing the problem to be intractable [22].”
Combinatorial Optimization on Graphs of Bounded Treewidth (2008, background): “For many graph problems, this parameterized variant is fixedparameter tractable (FPT) (for more information on fixedparameter tractability and complexity, see Downey and Fellows [17], Flum and Grohe [18], and Niedermeier [19]).”
Lower bounds based on the Exponential Time Hypothesis (2011, neutral): “A variant of ETH, called the Strong Exponential Time Hypothesis (SETH) can be used to give even more refined lower bounds saying, e.g., that a parameterized problem cannot be solved in time (2 ")knO(1) for any " > 1.”
A Multi-Facet Survey on Memetic Computation (2011, background): “Fixed-parameter algorithmics with kernelization techniques have also been proposed [155] for analyzing the given problem and divide the problem structure into smaller independent problem kernels that can be subsequently conquered and solved more efficiently.”
Infeasibility of instance compression and succinct PCPs for NP (2007, neutral): “There are a number of good reference works on parameterized complexity[10, 12, 21].”
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time (2011, neutral): “For instance in the case of Connected Vertex Cover the results show that the increase in running time to 1 ) algorithm of [67] for Vertex Cover is not an artifact of the Cut&Count technique, but rather an intrinsic characteristic of the problem.”
Invitation to data reduction and problem kernelization (2007, methodology): “Vertex Cover may be considered not only as the drosophila of fixed-parameter algorithmics [30], but also more specifically for the development of data reduction and kernelization techniques.”