| Popis: |
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4] , we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces (CSS-MSP, for short), which is defined as follows. In some constructing specific subgraph problem Q (CSS, for short), the objective is to choose a minimum-length subset of edges, such that these edges form a specific subgraph (such as a spanning tree or a Steiner tree). In the CSS-MSP problem Q ′ , these edges are further required to be cut from some stock pieces of length L, and the new objective, however, is to minimize the number of stock pieces of length L to construct all edges in such a specific subgraph. We obtain two main results. (1) Whenever the CSS problem Q can be approximated by an α-approximation algorithm ( α ≥ 1 ) (for the case α = 1 , the CSS problem Q is solved optimally by a polynomial-time exact algorithm), we design two approximation algorithms with performance ratios 2α and 7 α 4 to solve the CSS-MSP problem Q ′ ; (2) In addition, when the problem Q is to find a minimum spanning tree, we present a 3 2 -approximation algorithm and an APTAS to solve the problem Q ′ of constructing spanning tree with minimum number of length-bounded stock pieces. |
Full Text from ScienceDirect