Kernel Bounds for Disjoint Cycles and Disjoint Paths

DOI10.1007/978-3-642-04128-0_57MaRDI QIDQ3639278zbMATH OpenOpenAlexDBLPWikidataFDO

Authors A. Yeo, Hans L. Bodlaender, Stéphan Thomassé

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_57

Mathematics Subject Classification ID

Paths and cycles (05C38) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Kernel bounds for disjoint cycles and disjoint paths
• Kernel bounds for path and cycle problems
• Kernel bounds for path and cycle problems
• On Problems without Polynomial Kernels (Extended Abstract)
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs

Cited in

(36)

• Note on maximal bisection above tight lower bound
• A parameterized perspective on protecting elections
• Facility location problems: a parameterized view
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Parameterized algorithms for load coloring problem
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Hitting forbidden minors: approximation and kernelization
• Kernel bounds for path and cycle problems
• On the hardness of losing width
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• On the Kernelization Complexity of Colorful Motifs
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• Data reduction for graph coloring problems
• Parameterized complexity of vertex deletion into perfect graph classes
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• Kernelization: new upper and lower bound techniques
• Two edge modification problems without polynomial kernels
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Kernel bounds for path and cycle problems
• On the parameterized complexity of the repetition free longest common subsequence problem
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Parameterized Eulerian strong component arc deletion problem on tournaments
• Lower bounds on kernelization
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Quasi-Kernels for Oriented Paths and Cycles
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernelization of packing problems
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
• Kernel bounds for disjoint cycles and disjoint paths
• Solving MAX-\(r\)-SAT above a tight lower bound
• On the parameterized complexity of controlling amendment and successive winners
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Kernelization complexity of possible winner and coalitional manipulation problems in voting

This page was built for publication: Kernel Bounds for Disjoint Cycles and Disjoint Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639278)