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

1. Verfasser:
In: Optimization Letters, 10(2016), 6, S. 1337 - 1345
Format: E-Article
Sprache: Englisch
veröffentlicht: Springer Berlin Heidelberg
Schlagworte:
ISSN: 1862-4472
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
finc.format ElectronicArticle
finc.mega_collection Springer Journals
finc.id dswarm-105-MTAuMTAwNy9zMTE1OTAtMDE1LTA5MzUteQ
finc.record_id 10.1007/s11590-015-0935-y
finc.source_id 105
ris.type EJOUR
rft.atitle Approximations for constructing tree-form structures using specific material with fixed length
rft.eissn 1862-4480
rft.epage 1345
rft.genre article
rft.issn 1862-4472
rft.issue 6
rft.jtitle Optimization Letters
rft.pages 1337-1345
rft.place Berlin/Heidelberg
rft.pub Springer Berlin Heidelberg
rft.date 2016
x.date 2016-08-01T00:00:00Z
rft.stitle Optim Lett
rft.spage 1337
rft.volume 10
abstract 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 <InlineEquation ID="IEq2"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq2.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$G=(V,E; w)$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mrow xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">G</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">=</mo><mo stretchy="false" xmlns:xlink="http://www.w3.org/1999/xlink">(</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">V</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">,</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">E</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">;</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">w</mi><mo stretchy="false" xmlns:xlink="http://www.w3.org/1999/xlink">)</mo></mrow></math></EquationSource></InlineEquation>, a tree-form structure <InlineEquation ID="IEq3"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq3.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$\mathcal{S}$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mi mathvariant="script" xmlns:xlink="http://www.w3.org/1999/xlink">S</mi></math></EquationSource></InlineEquation> and some pieces of specific material with length <Emphasis Type="Italic">L</Emphasis>, where a length function <InlineEquation ID="IEq4"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq4.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$w:E\rightarrow Q^+$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mrow xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">w</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">:</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">E</mi><mo stretchy="false" xmlns:xlink="http://www.w3.org/1999/xlink">→</mo><msup xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">Q</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">+</mo></msup></mrow></math></EquationSource></InlineEquation>, satisfying <InlineEquation ID="IEq5"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq5.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$w(u,v) \le L$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mrow xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">w</mi><mo stretchy="false" xmlns:xlink="http://www.w3.org/1999/xlink">(</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">u</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">,</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">v</mi><mo stretchy="false" xmlns:xlink="http://www.w3.org/1999/xlink">)</mo><mo xmlns:xlink="http://www.w3.org/1999/xlink">≤</mo><mi xmlns:xlink="http://www.w3.org/1999/xlink">L</mi></mrow></math></EquationSource></InlineEquation> for each edge <Emphasis Type="Italic">uv</Emphasis> in <Emphasis Type="Italic">G</Emphasis>, we are asked how to construct a required tree-form structure <InlineEquation ID="IEq6"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq6.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$\mathcal{S}$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mi mathvariant="script" xmlns:xlink="http://www.w3.org/1999/xlink">S</mi></math></EquationSource></InlineEquation> as a subgraph <InlineEquation ID="IEq7"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq7.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$G'$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><msup xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">G</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">′</mo></msup></math></EquationSource></InlineEquation> of <Emphasis Type="Italic">G</Emphasis> such that each edge needed in <InlineEquation ID="IEq8"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq8.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$G'$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><msup xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">G</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">′</mo></msup></math></EquationSource></InlineEquation> 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 <InlineEquation ID="IEq9"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq9.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$G'$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><msup xmlns:xlink="http://www.w3.org/1999/xlink"><mi xmlns:xlink="http://www.w3.org/1999/xlink">G</mi><mo xmlns:xlink="http://www.w3.org/1999/xlink">′</mo></msup></math></EquationSource></InlineEquation>. For this new objective defined, we obtain three results: (1) We present a <InlineEquation ID="IEq10"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq10.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$\frac{3}{2}$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mfrac xmlns:xlink="http://www.w3.org/1999/xlink"><mn xmlns:xlink="http://www.w3.org/1999/xlink">3</mn><mn xmlns:xlink="http://www.w3.org/1999/xlink">2</mn></mfrac></math></EquationSource></InlineEquation>-approximation algorithm to construct a spanning tree of <Emphasis Type="Italic">G</Emphasis>; (2) We design a <InlineEquation ID="IEq11"><InlineMediaObject><ImageObject Type="Linedraw" Rendition="HTML" Format="GIF" FileRef="11590_2015_935_Article_IEq11.gif" Color="BlackWhite"/></InlineMediaObject><EquationSource Format="TEX">$$\frac{3}{2}$$</EquationSource><EquationSource Format="MATHML"><math xmlns:xlink="http://www.w3.org/1999/xlink"><mfrac xmlns:xlink="http://www.w3.org/1999/xlink"><mn xmlns:xlink="http://www.w3.org/1999/xlink">3</mn><mn xmlns:xlink="http://www.w3.org/1999/xlink">2</mn></mfrac></math></EquationSource></InlineEquation>-approximation algorithm to construct a single-source shortest paths tree of <Emphasis Type="Italic">G</Emphasis>; (3) We provide a 4-approximation algorithms to construct a metric Steiner tree of <Emphasis Type="Italic">G</Emphasis>.
authors Li Jianping
doi 10.1007/s11590-015-0935-y
languages eng
url https://doi.org/10.1007/s11590-015-0935-y
x.subjects Graph structures
Spanning tree
Single-source shortest paths tree
Metric Steiner tree
Approximation algorithms