Kernel bounds for disjoint cycles and disjoint paths
type: Item
instance of: scholarly article
title: Kernel bounds for disjoint cycles and disjoint paths
zbMATH Open document ID: 1221.68099
author: Hans L. Bodlaender
author: A. Yeo
author: Stéphan Thomassé
published in: Theoretical Computer Science
publication date: 2011-09-12T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5947155
zbMATH Keywords: data reduction
zbMATH Keywords: kernelization
zbMATH Keywords: fixed parameter complexity
zbMATH Keywords: disjoint cycles
zbMATH Keywords: algorithms
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.04.039
OpenAlex ID: W1976430052
cites work: The Moore bound for irregular graphs
cites work: Approximation algorithms for treewidth
cites work: A Cubic Kernel for Feedback Vertex Set
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: Q3113681
cites work: A Linear Kernel for Planar Feedback Vertex Set
cites work: A cubic kernel for feedback vertex set and loop cutset
cites work: On treewidth approximations.
cites work: The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
cites work: Lower bounds for kernelizations and other preprocessing procedures
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Incompressibility through Colors and IDs
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4393480
cites work: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Q4414505
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Parameterized and Exact Computation
cites work: Graph minors. XIII: The disjoint paths problem
cites work: A 4 k 2 kernel for feedback vertex set
Wikidata QID: Q59567600
DOI: 10.1016/J.TCS.2011.04.039
DBLP publication ID: journals/tcs/BodlaenderTY11
description: scientific article; zbMATH DE number 5947155