A Problem Kernelization for Graph Packing

DOI10.1007/978-3-540-95891-8_37zbMath1206.68239OpenAlexW1519122062MaRDI QIDQ3599088

Hannes Moser

Publication date: 3 February 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-95891-8_37

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

Edge-disjoint packing of stars and cycles ⋮ A parameterized perspective on packing paths of length two ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Planar graph vertex partition for linear problem kernels ⋮ An improved kernel for planar vertex-disjoint triangle packing ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Packing paths: recycling saves time ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Explicit linear kernels for packing problems ⋮ Arbitrary Overlap Constraints in Graph Packing Problems ⋮ Kernels for packing and covering problems ⋮ A kernelization algorithm for \(d\)-hitting set ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ On Generating Triangle-Free Graphs ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Triangle packing in (sparse) tournaments: approximation and kernelization ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph-modeled data clustering: Exact algorithms for clique generation
• Looking at the stars
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Applying modular decomposition to parameterized cluster editing problems
• Packing triangles in low degree graphs and indifference graphs
• Vertex Cover: Further Observations and Further Improvements
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• On Problems without Polynomial Kernels (Extended Abstract)
• Faster Algebraic Algorithms for Path and Packing Problems
• Divide-and-Color
• A Cubic Kernel for Feedback Vertex Set
• Kernelization Algorithms for d-Hitting Set Problems
• A More Effective Linear Kernelization for Cluster Editing
• Vertex packings: Structural properties and algorithms
• On the completeness of a generalized matching problem
• Efficient Parameterized Preprocessing for Cluster Editing
• A Parameterized Perspective on Packing Paths of Length Two
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: A Problem Kernelization for Graph Packing