Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
type: Item
instance of: scholarly article
title: Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
zbMATH Open document ID: 1252.05100
author: Marek Cygan
author: Marcin Pilipczuk
author: Michał Pilipczuk
author: Jakub Onufry Wojtaszczyk
published in: Discrete Applied Mathematics
publication date: 2012-10-26T00:00:00Z
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6099340
zbMATH Keywords: degenerate graphs
zbMATH Keywords: kernelization
zbMATH Keywords: connected dominating set
zbMATH Keywords: graph motif
MaRDI profile type: Publication
full work available at URL: j.dam.2012.05.016
OpenAlex ID: W2057205207
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: On the Kernelization Complexity of Colorful Motifs
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Q3113681
cites work: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Nondeterminism within $P^ * $
cites work: Vertex cover: Further observations and further improvements
cites work: Parameterized Complexity of Eulerian Deletion Problems
cites work: Q5743378
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Incompressibility through Colors and IDs
cites work: Q4393480
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
cites work: Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
cites work: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
cites work: Bidimensionality and Geometric Graphs
cites work: Q5743379
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Parameterized Complexity for Domination Problems on Degenerate Graphs
cites work: Q5743381
cites work: Q4142699
cites work: Lower bound of the Hadwiger number of graphs by their average degree
cites work: Q5743382
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: FPT Algorithms for Connected Feedback Vertex Set
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
cites work: Q3108579
cites work: An extremal function for contractions of graphs
cites work: The extremal function for complete minors
cites work: A 4 k 2 kernel for feedback vertex set
DOI: 10.1016/J.DAM.2012.05.016
description: scientific article; zbMATH DE number 6099340