首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Approximation algorithms for constructing some required structures in digraphs
Authors:Jianping Li  Yu Ge  Shuai He  Junran Lichen
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号