Exploiting c-Closure in Kernelization Algorithms for Graph Problems
From MaRDI portal
Publication:5874537
Recommendations
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Kernels in graphs with a clique-cutset
- On graph kernels: hardness results and efficient alternatives.
- Essentially tight kernels for (weakly) closed graphs
- On computing graph closures
- On the computational complexity of graph closures
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- On the kernelization of split graph problems
- A note on computing graph closures
Cites work
- scientific article; zbMATH DE number 3869067 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Boundary classes of graphs for the dominating set problem
- Crown reductions for the minimum weighted vertex cover problem
- Crown structures for vertex cover kernelization
- Extremal combinatorics. With applications in computer science
- FPT algorithms for domination in biclique-free graphs
- Finding cliques in social networks: a new distribution-free model
- Fundamentals of parameterized complexity
- Graph-Theoretic Concepts in Computer Science
- Improved induced matchings in sparse graphs
- Kernelization of packing problems
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- New results on maximum induced matchings in bipartite graphs and beyond
- On the induced matching problem
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parameterized algorithms
- Parameterized complexity of finding regular induced subgraphs
- Perfect Code is \(W[1]\)-complete
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Some remarks on the theory of graphs
- The complexity of irredundant sets parameterized by size
- The parameterized complexity of the induced matching problem
- Tight kernel bounds for problems on graphs with small degeneracy
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
Cited in
(6)- Twin-width and polynomial kernels
- Kernels in graphs with a clique-cutset
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- scientific article; zbMATH DE number 7765378 (Why is no real title available?)
This page was built for publication: Exploiting c-Closure in Kernelization Algorithms for Graph Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874537)
