Crown structures for vertex cover kernelization

DOI10.1007/s00224-007-1328-0zbMath1148.68035OpenAlexW1974692335WikidataQ57359941 ScholiaQ57359941MaRDI QIDQ2464323

Michael R. Fellows, Michael A. Langston, W. Henry Suters, Faisal N. Abu-Khzam

Publication date: 19 December 2007

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-1328-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Linear kernels for separating a graph into components of bounded size, A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Autarkies and Persistencies for QUBO, A Basic Parameterized Complexity Primer, On the kernelization of split graph problems, A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition, Critical sets, crowns and local maximum independent sets, On a generalization of Nemhauser and Trotter's local optimization theorem, Reoptimization of parameterized problems, From matchings to independent sets, Critical and maximum independent sets of a graph, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes, Preprocessing to reduce the search space: antler structures for feedback vertex set, Separator-based data reduction for signed graph balancing, Kernelization for feedback vertex set via elimination distance to a forest, Data Reduction for Maximum Matching on Real-World Graphs, Kernelization for feedback vertex set via elimination distance to a forest, On upper bounds for the independent transversal domination number, On the Parameterized Parallel Complexity and the Vertex Cover Problem, On bounded block decomposition problems for under-specified systems of equations, A generalization of Nemhauser and Trotter's local optimization theorem, Kernelization of Two Path Searching Problems on Split Graphs, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments, Improved kernel results for some FPT problems based on simple observations, Crowns in bipartite graphs, Kernels for packing and covering problems, A kernelization algorithm for \(d\)-hitting set, Hitting Forbidden Minors: Approximation and Kernelization, Parameterized certificate dispersal and its variants, On the Power of Simple Reductions for the Maximum Independent Set Problem, FPT is characterized by useful obstruction sets, An improved kernelization algorithm for \(r\)-set packing, Efficient parallel algorithms for parameterized problems, Kernelization: New Upper and Lower Bound Techniques, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, Nearly optimal robust secret sharing against rushing adversaries