کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478263 | 1446040 | 2014 | 8 صفحه PDF | دانلود رایگان |
• We consider a new problem of constructing some required structures in digraphs.
• The objective is to minimize the number of pieces of a specific material with length L.
• Up to now, it is the first time to consider this new model.
• We design four (asymptotic) approximation algorithms to construct the two structures.
• We propose two conjectures for these required structures in digraphs.
We consider a new problem of constructing some required structures in digraphs, where all arcs installed in such required structures are supposed to be cut from some pieces of a specific material of length L. Formally, we consider the model: a digraph D = (V, A; w), a structure S and a specific material of length L, where w: A → R+, we are asked to construct a subdigraph D′ from D, having the structure S, such that each arc in D′ is constructed by a part of a piece or/and some whole pieces of such a specific material, the objective is to minimize the number of pieces of such a specific material to construct all arcs in D′.For the two required structures: (1) a directed path from a node s to a node t and (2) a strongly connected spanning subdigraph, we design four approximation algorithms with constant performance ratios to solve the both problems, respectively.
Journal: European Journal of Operational Research - Volume 232, Issue 2, 16 January 2014, Pages 307–314