Exploiting c-Closure in Kernelization Algorithms for Graph Problems
type: Item
instance of: scholarly article
author: Tomohiro Koana
author: Christian Komusiewicz
author: Frank Sommer
publication date: 2023-02-07T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7651204
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: kernelization
zbMATH Keywords: \(c\)-closure
zbMATH Keywords: dominating set
zbMATH Keywords: induced matching
zbMATH Keywords: irredundant set
zbMATH Keywords: Ramsey numbers
MaRDI profile type: Publication
full work available at URL: LIPIcs-ESA-2020-65.pdf
OpenAlex ID: W3082339973
title: Exploiting c-Closure in Kernelization Algorithms for Graph Problems
cites work: Crown structures for vertex cover kernelization
cites work: Boundary classes of graphs for the dominating set problem
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: Q3337224
cites work: Perfect Code is \(W[1]\)-complete
cites work: Vertex cover: Further observations and further improvements
cites work: Crown reductions for the minimum weighted vertex cover problem
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Parameterized Algorithms
cites work: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
cites work: New results on maximum induced matchings in bipartite graphs and beyond
cites work: Q5743378
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Fundamentals of parameterized complexity
cites work: The complexity of irredundant sets parameterized by size
cites work: Some remarks on the theory of graphs
cites work: Improved induced matchings in sparse graphs
cites work: Finding Cliques in Social Networks: A New Distribution-Free Model
cites work: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
cites work: Parameterized Complexity for Domination Problems on Degenerate Graphs
cites work: Q5743381
cites work: Extremal Combinatorics
cites work: On the induced matching problem
cites work: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
cites work: The parameterized complexity of the induced matching problem
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: Vertex packings: Structural properties and algorithms
cites work: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: FPT Algorithms for Domination in Biclique-Free Graphs
DOI: 10.4230/LIPICS.ESA.2020.65
Recommended article: Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems
Recommended article: Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
Recommended article: Kernels in graphs with a clique-cutset
Recommended article: Learning Theory and Kernel Machines
Recommended article: Essentially tight kernels for (weakly) closed graphs
Recommended article: On computing graph closures
Recommended article: On the computational complexity of graph closures
Recommended article: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
Recommended article: On the kernelization of split graph problems
Recommended article: A note on computing graph closures
description: scientific article; zbMATH DE number 7651204