Approximations for constructing tree-form structures using specific material with fixed length

作者：Li, Jianping^*; Guan, Li; Ding, Honglin; Li, Weidong

来源：Optimization Letters, 2016, 10(6): 1337-1345.

DOI：10.1007/s11590-015-0935-y

• Graph structures
• Spanning tree
• Single-source shortest paths tree
• Metric Steiner tree
• Approximation algorithms

Substituting for the ordinary objective to minimize the sum of lengths of all edges in some graph structure of a weighted graph, we propose a new problem of constructing certain tree-form structure in same graph, where all edges needed in such a tree-form structure are supposed to be cut from some pieces of a specific material with fixed length. More precisely, we study a new problem defined as follows: a weighted graph G = (V, E; w), a tree-form structure S and some pieces of specific material with length L, where a length function w : E -> Q(+), satisfying w(u, v) <= L for each edge uv in G, we are asked how to construct a required tree-form structure S as a subgraph G' of G such that each edge needed in G' is constructed by a part of a piece of such a specific material, the new objective is to minimize the number of necessary pieces of such a specific material to construct all edges in G'. For this new objective defined, we obtain three results: (1) We present a 3/2-approximation algorithm to construct a spanning tree of G; (2) We design a 3/2-approximation algorithm to construct a single-source shortest paths tree of G; (3) We provide a 4-approximation algorithms to construct a metric Steiner tree of G.

• 出版日期2016-8
• 单位云南大学