On Approximations for Constructing Required Subgraphs Using Stock Pieces of Fixed Length

In this paper, we consider the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a variant of the problem of minimum-cost edge-weighted subgraph constructions (MCEWSC, for short). This new problem has many important applications in our reality life, and it is defined as follows. In the MCEWSC problem Q, the objective is to choose a minimum-cost subset of edges from a graph such that these edges form a required subgraph (e.g., a spanning tree). In the CRS-SPFL problem \(Q^{\prime }\), these edges are further required to be constructed by some stock pieces of fixed length L, the new objective is to minimize the total cost to construct such a required subgraph \(G'\), where the total cost is sum of the cost to buy necessary these stock pieces and the cost to construct all edges in such a subgraph \(G'\).