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

1. Verfasser: Li, Jianping Optimization Letters, 10(2016), 6, S. 1337 - 1345 E-Article Englisch Springer Berlin Heidelberg 1862-4472 Keine Tags, Fügen Sie den ersten Tag hinzu!
finc.format ElectronicArticle Springer Journals dswarm-105-MTAuMTAwNy9zMTE1OTAtMDE1LTA5MzUteQ 10.1007/s11590-015-0935-y 105 EJOUR Approximations for constructing tree-form structures using specific material with fixed length 1862-4480 1345 article 1862-4472 6 Optimization Letters 1337-1345 Berlin/Heidelberg Springer Berlin Heidelberg 2016 2016-08-01T00:00:00Z Optim Lett 1337 10 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)$$G=(V,E;w)[/itex], a tree-form structure $$\mathcal{S}$$S[/itex] and some pieces of specific material with length L, where a length function $$w:E\rightarrow Q^+$$w:EQ+[/itex], satisfying $$w(u,v) \le L$$w(u,v)L[/itex] for each edge uv in G, we are asked how to construct a required tree-form structure $$\mathcal{S}$$S[/itex] as a subgraph $$G'$$G[/itex] of G such that each edge needed in $$G'$$G[/itex] 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'$$G[/itex]. For this new objective defined, we obtain three results: (1) We present a $$\frac{3}{2}$$32[/itex]-approximation algorithm to construct a spanning tree of G; (2) We design a $$\frac{3}{2}$$32[/itex]-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. Li Jianping 10.1007/s11590-015-0935-y eng https://doi.org/10.1007/s11590-015-0935-y Graph structures Spanning tree Single-source shortest paths tree Metric Steiner tree Approximation algorithms