Approximation algorithms for constructing some required structures in digraphs |
| |
Authors: | Jianping Li Yu Ge Shuai He Junran Lichen |
| |
Affiliation: | 1. Department of Mathematics, Yunnan University, Kunming 650091, PR China;2. School of Economics, Yunnan University, Kunming 650091, PR China |
| |
Abstract: | 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′. |
| |
Keywords: | Combinatorial optimization Digraph Structure construction Inapproximability (Asymptotic) approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|