Polynomial kernels for vertex cover parameterized by small degree modulators
type: Item
instance of: scholarly article
title: Polynomial kernels for vertex cover parameterized by small degree modulators
zbMATH Open document ID: 1419.05179
author: Diptapriyo Majumdar
author: Venkatesh Raman
author: Saket Saurabh
published in: Theory of Computing Systems
publication date: 2019-09-05T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7101694
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: expansion lemma
zbMATH Keywords: vertex cover
zbMATH Keywords: structural parameterization
MaRDI profile type: Publication
full work available at URL: s00224-018-9858-1
OpenAlex ID: W2790946280
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
cites work: Parameterized complexity of vertex colouring
cites work: Improved upper bounds for vertex cover
cites work: Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
cites work: Parameterized Algorithms
cites work: On the hardness of losing width
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Fundamentals of parameterized complexity
cites work: Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: The complexity ecology of parameters: An illustration using bounded max leaf number
cites work: Hitting forbidden minors: approximation and kernelization
cites work: Vertex Cover Structural Parameterization Revisited
cites work: A polynomial algorithm for the max-cut problem on graphs without long odd cycles
cites work: A probabilistic approach to problems parameterized above or below tight bounds
cites work: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
cites work: Smaller Parameters for Vertex Cover Kernelization
cites work: A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
cites work: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
cites work: Sparsification upper and lower bounds for graph problems and not-all-equal SAT
cites work: Improved Parameterized Algorithms for above Average Constraint Satisfaction
cites work: A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
cites work: Representative Sets and Irrelevant Vertices
cites work: Faster Parameterized Algorithms Using Linear Programming
cites work: Q5363786
cites work: Vertex packings: Structural properties and algorithms
cites work: On the Kernelization Complexity of Problems on Graphs without Long Odd Cycles
cites work: Q3392273
cites work: A 4 k 2 kernel for feedback vertex set
Wikidata QID: Q130065750
DOI: 10.1007/S00224-018-9858-1
Recommended article: Q5363786
Recommended article: A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
Recommended article: Smaller Parameters for Vertex Cover Kernelization
Recommended article: Q3113682
Recommended article: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
Recommended article: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
Recommended article: A kernel of order \(2k - c\) for Vertex Cover
Recommended article: Partially Polynomial Kernels for Set Cover and Test Cover
Recommended article: A Randomized Polynomial Kernel for Subset Feedback Vertex Set
description: scientific article