Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
DOI10.1145/2786015zbMATH Open1347.68353OpenAlexW2257188417MaRDI QIDQ2828236FDOQ2828236
Authors: Henning Fernau, Jazmín Romero, Alejandro Lopez-Ortiz 
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2786015
Recommendations
- Kernelization algorithms for packing problems allowing overlaps
- Parameterized algorithms for the \(H\)-packing with \(t\)-overlap problem
- The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
- A parameterized algorithm for packing overlapping subgraphs
- Arbitrary overlap constraints in graph packing problems
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A Problem Kernelization for Graph Packing
- On the completeness of a generalized matching problem
- Graph-Theoretic Concepts in Computer Science
- Looking at the stars
- Graph-based data clustering with overlaps
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Kernels for Packing and Covering Problems
- A parameterized perspective on packing paths of length two
- An improved kernelization for \(P_{2}\)-packing
- An improved kernelization algorithm for \(r\)-set packing
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- The NP-Completeness of Some Edge-Partition Problems
- Another look at the degree constrained subgraph problem
- Packing triangles in bounded degree graphs.
- A parameterized algorithm for packing overlapping subgraphs
Cited In (6)
- Parameterized algorithms for the \(H\)-packing with \(t\)-overlap problem
- The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
- A parameterized algorithm for packing overlapping subgraphs
- Arbitrary overlap constraints in graph packing problems
- Kernelization algorithms for packing problems allowing overlaps
- Kernels for packing and covering problems
This page was built for publication: Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828236)
