The kernelization complexity of connected domination in graphs with (no) small cycles
type: Item
instance of: scholarly article
title: The kernelization complexity of connected domination in graphs with (no) small cycles
zbMATH Open document ID: 1318.68096
author: Neeldhara Misra
author: Geevarghese Philip
author: Venkatesh Raman
author: Saket Saurabh
published in: Algorithmica
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6375639
zbMATH Keywords: connected dominating set
zbMATH Keywords: kernelization
zbMATH Keywords: girth
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: kernel lower bounds
MaRDI profile type: Publication
full work available at URL: s00453-012-9681-z
OpenAlex ID: W2083586074
cites work: Polynomial-time data reduction for dominating set
cites work: Computational Complexity
cites work: On Problems without Polynomial Kernels (Extended Abstract)
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
cites work: Domination problems in nowhere-dense classes of graphs
cites work: Q5315023
cites work: Incompressibility through Colors and IDs
cites work: Q4503944
cites work: The steiner problem in graphs
cites work: Bidimensionality and Geometric Graphs
cites work: Q3549693
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: Parameterized Complexity for Domination Problems on Degenerate Graphs
cites work: Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
cites work: Domination When the Stars Are Out
cites work: Reducibility among Combinatorial Problems
cites work: Linear Kernel for Planar Connected Dominating Set
cites work: A linear kernel for a planar connected dominating set
cites work: An Improved Kernel for Planar Connected Dominating Set
cites work: The effect of girth on the kernelization complexity of connected dominating set
cites work: Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: Graph minors. VIII: A Kuratowski theorem for general surfaces
cites work: Graph minors. XX: Wagner's conjecture
cites work: A simpler proof of the excluded minor theorem for higher surfaces
DOI: 10.1007/S00453-012-9681-Z
description: scientific article; zbMATH DE number 6375639