Kernelization for edge triangle packing and covering via a discharging method

DOI10.1016/j.tcs.2024.114635MaRDI QIDQ6558639

Zimo Sheng, Mingyu Xiao

Publication date: 19 June 2024

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

zbMATH Keywords

kernelizationdischarging methodcrown decompositionedge triangle coveringedge triangle packing

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Maximum bounded \(H\)-matching is Max SNP-complete
• A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing
• Parameterized algorithms and kernels for almost induced matching
• Towards optimal kernel for edge-disjoint triangle packing
• On Generating Triangle-Free Graphs
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• 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
• The NP-Completeness of Some Edge-Partition Problems
• Approximation algorithms for NP-complete problems on planar graphs
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• Parameterized Algorithms

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