Using parametric transformations toward polynomial kernels for packing problems allowing overlaps

DOI10.1145/2786015MaRDI QIDQ2828236zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

overlapkernelsgraph packingset packingpolynomial parametric transformations

Mathematics Subject Classification ID

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)

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

Cites work

• A Problem Kernelization for Graph Packing
• A parameterized algorithm for packing overlapping subgraphs
• A parameterized perspective on packing paths of length two
• An improved kernelization algorithm for \(r\)-set packing
• An improved kernelization for \(P_{2}\)-packing
• Another look at the degree constrained subgraph problem
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph-Theoretic Concepts in Computer Science
• Graph-based data clustering with overlaps
• Kernels for Packing and Covering Problems
• Looking at the stars
• On the completeness of a generalized matching problem
• Packing triangles in bounded degree graphs.
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(6)

• Parameterized algorithms for the \(H\)-packing with \(t\)-overlap problem
• A parameterized algorithm for packing overlapping subgraphs
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
• Kernelization algorithms for packing problems allowing overlaps
• Arbitrary overlap constraints in graph packing problems
• 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)