Approximation algorithms for constructing some required structures in digraphs

• 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.