Kernel(s) for problems with no kernel

DOI10.1145/2344422.2344428zbMath1295.68120DBLPjournals/talg/Binkele-RaibleFFLSV12OpenAlexW1999681430WikidataQ60488494 ScholiaQ60488494MaRDI QIDQ3189081

Yngve Villanger, Daniel Binkele-Raible, Henning Fernau, Saket Saurabh, Fedor V. Fomin, Daniel Lokshtanov

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2344422.2344428

zbMATH Keywords

lower boundsparameterized algorithmskernelizationout-branchingmax-leaf spanning tree

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (23)

Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Reoptimization of parameterized problems ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Parameterized certificate dispersal and its variants ⋮ On some FPT problems without polynomial Turing compressions ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Basic Terminology, Notation and Results ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Leafy spanning arborescences in DAGs ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

This page was built for publication: Kernel(s) for problems with no kernel