Edge-disjoint packing of stars and cycles
From MaRDI portal
Publication:2629232
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
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