On problems without polynomial kernels
type: Item
instance of: scholarly article
title: On problems without polynomial kernels
zbMATH Open document ID: 1192.68288
author: Hans L. Bodlaender
author: Rodney G. Downey
author: Michael R. Fellows
author: Danny Hermelin
published in: Journal of Computer and System Sciences
publication date: 2009-11-10T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5629238
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: polynomial kernels
zbMATH Keywords: lower bounds
zbMATH Keywords: distillation algorithm
zbMATH Keywords: composition algorithm
zbMATH Keywords: polynomial hierarchy
Wikidata QID: Q57359819
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.04.001
OpenAlex ID: W2107284348
cites work: Polynomial-time data reduction for dominating set
cites work: Color-coding
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Q3221758
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: A Cubic Kernel for Feedback Vertex Set
cites work: Mathematical Foundations of Computer Science 2003
cites work: The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
cites work: Advice classes of parametrized tractability
cites work: Q4535023
cites work: Computation Models for Parameterized Complexity
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: STACS 2005
cites work: Linear FPT reductions and computational lower bounds
cites work: The complexity of theorem-proving procedures
cites work: The importance of being biased
cites work: Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
cites work: Q4393480
cites work: Q4886099
cites work: Nonconstructive advances in polynomial-time complexity
cites work: On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
cites work: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
cites work: Parametrized complexity theory.
cites work: Automata, Languages and Programming
cites work: Q3549693
cites work: The complexity of first-order and monadic second-order logic revisited
cites work: Q4198056
cites work: Graph-modeled data clustering: Exact algorithms for clique generation
cites work: Fixed-parameter tractability and data reduction for multicut in trees
cites work: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
cites work: Algorithms and Data Structures
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Divide-and-Color
cites work: On self-reducibility and weak P-selectivity
cites work: On the Structure of Polynomial Time Reducibility
cites work: Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
cites work: Vertex packings: Structural properties and algorithms
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: Q4028099
cites work: Q4228512
cites work: The polynomial-time hierarchy
cites work: Q4633817
DOI: 10.1016/J.JCSS.2009.04.001
description: scientific article; zbMATH DE number 5629238