Kernelization for edge triangle packing and covering via a discharging method

DOI10.1016/J.TCS.2024.114635MaRDI QIDQ6558639zbMATH OpenFDO

Authors Zimo Sheng, Mingyu Xiao

Publication date 19 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114635

zbMATH Keywords

crown decompositiondischarging methodedge triangle coveringedge triangle packingkernelization

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Parameterized and Exact Computation
• Towards optimal kernel for edge-disjoint triangle packing
• An improved kernel for planar vertex-disjoint triangle packing
• A Problem Kernelization for Graph Packing

Cites work

• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Approximation algorithms for NP-complete problems on planar graphs
• scientific article; zbMATH DE number 6857816 (Why is no real title available?)
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Maximum bounded \(H\)-matching is Max SNP-complete
• On generating triangle-free graphs
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Parameterized algorithms
• Parameterized algorithms and kernels for almost induced matching
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• The NP-Completeness of Some Edge-Partition Problems
• Towards optimal kernel for edge-disjoint triangle packing

This page was built for publication: Kernelization for edge triangle packing and covering via a discharging method

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