Edge-disjoint packing of stars and cycles

DOI10.1016/J.TCS.2016.06.001zbMATH Open1344.68097OpenAlexW2538915965MaRDI QIDQ2629232FDOQ2629232

Authors Ge Xia, Yong Zhang, Minghui 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

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

Recommendations

• Edge-disjoint packing of stars and cycles
• Parameterized and Exact Computation
• Looking at the stars
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Parameterized and Exact Computation

Cites work

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

Cited in

(11)

• Edge-disjoint packing of stars and cycles
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Kernelization of cycle packing with relaxed disjointness constraints
• Geodesic packing in graphs
• Kernelization of cycle packing with relaxed disjointness constraints
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• The parameterized complexity of cycle packing: indifference is not an issue
• Looking at the stars
• New kernels for several problems on planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629232)