A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing
From MaRDI portal
Publication:1628680
DOI10.1016/j.ipl.2018.10.006zbMath1469.68075OpenAlexW2896541981MaRDI QIDQ1628680
Publication date: 5 December 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.10.006
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- On a generalization of Nemhauser and Trotter's local optimization theorem
- Planar graph vertex partition for linear problem kernels
- A \(2k\) kernel for the cluster editing problem
- Maximum bounded \(H\)-matching is Max SNP-complete
- Linear kernels for separating a graph into components of bounded size
- Towards optimal kernel for edge-disjoint triangle packing
- Crown structures for vertex cover kernelization
- Parametrized complexity theory.
- Vertex Cover: Further Observations and Further Improvements
- TWO THEOREMS IN GRAPH THEORY
- 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
- Vertex packings: Structural properties and algorithms
- Approximation algorithms for NP-complete problems on planar graphs
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Efficient Parameterized Preprocessing for Cluster Editing
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing
