Towards optimal kernel for edge-disjoint triangle packing

DOI10.1016/j.ipl.2014.02.003zbMath1284.68285OpenAlexW2017799420MaRDI QIDQ2446590

Yongjie Yang

Publication date: 17 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.02.003

zbMATH Keywords

graph algorithmskernelizationfixed-parameter tractabletriangle packinglinear kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Edge-disjoint packing of stars and cycles ⋮ On the kernelization of split graph problems ⋮ A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ An improved kernel for planar vertex-disjoint triangle packing ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller

Cites Work

• Unnamed Item
• Planar graph vertex partition for linear problem kernels
• Lower bounds on kernelization
• Cluster editing: kernelization based on edge cuts
• Packing triangles in bounded degree graphs.
• Solving large FPT problems on coarse-grained parallel machines
• A linear vertex kernel for maximum internal spanning tree
• Towards optimal kernel for connected vertex cover in planar graphs
• Parametrized complexity theory.
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernelization – Preprocessing with a Guarantee
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Kernelization: New Upper and Lower Bound Techniques
• The NP-Completeness of Some Edge-Partition Problems
• Parameterized and Exact Computation
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

This page was built for publication: Towards optimal kernel for edge-disjoint triangle packing