Towards optimal kernel for edge-disjoint triangle packing

DOI10.1016/J.IPL.2014.02.003MaRDI QIDQ2446590zbMATH OpenOpenAlexFDO

Authors 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

fixed-parameter tractablegraph algorithmskernelizationlinear kerneltriangle packing

Mathematics Subject Classification ID

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

Recommendations

• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Parameterized and Exact Computation
• A Problem Kernelization for Graph Packing
• Graph-Theoretic Concepts in Computer Science
• Planar vertex-disjoint cycle packing: new structures and improved kernel

Cites work

• A linear vertex kernel for maximum internal spanning tree
• Cluster editing: kernelization based on edge cuts
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Kernelization -- preprocessing with a guarantee
• Kernelization: new upper and lower bound techniques
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Lower bounds on kernelization
• Packing triangles in bounded degree graphs.
• Parameterized and Exact Computation
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Parametrized complexity theory.
• Planar graph vertex partition for linear problem kernels
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Solving large FPT problems on coarse-grained parallel machines
• The NP-Completeness of Some Edge-Partition Problems
• Towards optimal kernel for connected vertex cover in planar graphs

Cited in

(16)

• A (3+)k-vertex kernel for edge-disjoint triangle packing
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• Packing triangles in low degree graphs and indifference graphs
• Edge-disjoint packing of stars and cycles
• On the kernelization of split graph problems
• An improved kernel for planar vertex-disjoint triangle packing
• Edge-disjoint packing of stars and cycles
• A Problem Kernelization for Graph Packing
• Kernelization of two path searching problems on split graphs
• A 42k kernel for the complementary maximal strip recovery problem
• Triangle packing in (sparse) tournaments: approximation and kernelization
• Parameterized and Exact Computation
• Kernelization for edge triangle packing and covering via a discharging method
• A discharging method: improved kernels for edge triangle packing and covering
• Approximate Turing kernelization for problems parameterized by treewidth

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

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