Issue |
RAIRO-Oper. Res.
Volume 55, Number 4, July-August 2021
|
|
---|---|---|
Page(s) | 2129 - 2140 | |
DOI | https://doi.org/10.1051/ro/2021096 | |
Published online | 08 July 2021 |
On star family packing of graphs
School of Mathematics, Southeast University, Nanjing 210096, P.R. China
* Corresponding author: wslin@seu.edu.cn
Received:
16
March
2021
Accepted:
23
June
2021
Let ℋ be a family of graphs. An ℋ-packing of a graph G is a set {G1, G2,…,Gk} of disjoint subgraphs of G such that each Gj is isomorphic to some element of ℋ. An ℋ-packing of a graph G that covers the maximum number of vertices of G is called a maximum ℋ-packing of G. The ℋ-packing problem seeks to find a maximum ℋ-packing of a graph. Let i be a positive integer. An i-star is a complete bipartite graph K1,i. This paper investigates the ℋ-packing problem with H being a family of stars. For an arbitrary family 𝒮 of stars, we design a linear-time algorithm for the 𝒮-packing problem in trees. Let t be a positive integer. An ℋ-packing is called a t+-star packing if ℋ consists of i-stars with i ≥ t. We show that the t+-star packing problem for t ≥ 2 is NP-hard in bipartite graphs. As a consequence, the 2+-star packing problem is NP-hard even in bipartite graphs with maximum degree at most 4. Let T and t be two positive integers with T > t. An ℋ-packing is called a T\t-star packing if ℋ={K1,1,K1,2,…,K1,T}\{K1,t}. For t ≥ 2, we present a t/t+1-approximation algorithm for the T\t-star packing problem that runs in 𝒪(mn1/2) time, where n is the number of vertices and m the number of edges of the input graph. We also design a 1/2-approximation algorithm for the 2+-star packing problem that runs in 𝒪(m) time, where m is the number of edges of the input graph. As a consequence, every connected graph with at least 3 vertices has a 2+-star packing that covers at least half of its vertices.
Mathematics Subject Classification: 05C70 / 68R10
Key words: Star / tree / H-packing / star family packing / t+-star packing / T\t-star packing
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.