Edge-disjoint packing of stars and cycles

DOI10.1016/j.tcs.2016.06.001zbMath1344.68097OpenAlexW2538915965MaRDI QIDQ2629232

Yong Zhang, Ge Xia, Ming-Hui Jiang

Publication date: 5 July 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.001

zbMATH Keywords

parameterized complexitykernelizationgraph packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Geodesic packing in graphs ⋮ New kernels for several problems on planar graphs

Cites Work

• On a generalization of Nemhauser and Trotter's local optimization theorem
• Fundamentals of parameterized complexity
• Kernel bounds for disjoint cycles and disjoint paths
• A generalization of Nemhauser and Trotter's local optimization theorem
• Chain packing in graphs
• Looking at the stars
• Faster fixed-parameter tractable algorithms for matching and packing problems
• On the complexity of partitioning graphs into connected subgraphs
• Edge-packing in planar graphs
• Bin packing with fixed number of bins revisited
• Towards optimal kernel for edge-disjoint triangle packing
• Kernels for Packing and Covering Problems
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Polynomial-time data reduction for dominating set
• A Problem Kernelization for Graph Packing
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• The NP-Completeness of Some Edge-Partition Problems
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• (Meta) Kernelization
• Parameterized and Exact Computation
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Edge-disjoint packing of stars and cycles