Some network enlargement problems  

作　　者：杨晓光 

机构地区：[1]Institute of Sjstems Science, Chinese Academy of Sciences, Beijing 100080, China

出　　处：《Chinese Science Bulletin》1996年第20期1676-1678,共3页

摘　　要：First we introduce some notations. Assume that N=(V, A, c) is a network, with vertex set V, arc set A, capacity c: A R^+. Suppose that a positive increment of the capacity c(e) will incur two costs, setup cost s(e) and linear cost w(e), and the increment is limited by d(e). Given a balance function b: V→R such that the first enlargement problem is to enlarge the capacity c to c~* such that (1) the network can have a flow to guarantee the balance function with respect to c~*; (2) c~*(e)-c(e)≤d(e), (?)e∈A;

关 键 词：NETWORK ENLARGEMENT minimum COST flow NP-hrd combinatorial STRONGLY POLYNOMIAL algorithm. 

分 类 号：TN915[电子电信—通信与信息系统]