Kernelization Algorithms for Packing Problems Allowing Overlaps

DOI10.1007/978-3-319-17142-5_35zbMath1460.68074arXiv1411.6915OpenAlexW1588413154MaRDI QIDQ2948487

Henning Fernau, Jazmín Romero, Alejandro López-Ortiz

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.6915

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Scheduling split intervals with non-uniform demands ⋮ Explicit linear kernels for packing problems

Cites Work

• Unnamed Item
• Graph-based data clustering with overlaps
• An improved kernelization algorithm for \(r\)-set packing
• Looking at the stars
• A parameterized perspective on packing paths of length two
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Another look at the degree constrained subgraph problem
• Kernelization Algorithms for Packing Problems Allowing Overlaps
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• A Problem Kernelization for Graph Packing
• A Parameterized Algorithm for Packing Overlapping Subgraphs
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science
• The ${\mathcal{G}}$ -Packing with t-Overlap Problem

This page was built for publication: Kernelization Algorithms for Packing Problems Allowing Overlaps