Let G<sub>1</sub> and G<sub>2</sub> be finite digraphs,both with vertex set V.Suppose that each vertexv of V has nonnegative integers f（v） and g（v） with f（v）≤g（v）,and each arc e of G&l...Let G<sub>1</sub> and G<sub>2</sub> be finite digraphs,both with vertex set V.Suppose that each vertexv of V has nonnegative integers f（v） and g（v） with f（v）≤g（v）,and each arc e of G<sub>4</sub> hasnonnegative integers a<sub>i</sub>（e） and b<sub>i</sub>（e） with a<sub>i</sub>（e）≤b<sub>i</sub>（e）,i=1,2.In this paper we give anecessary and sufficient condition for the existence of k arborescences in G<sub>4</sub> covering each are（?） of G<sub>i</sub> at least a<sub>i</sub>（e） and at most b<sub>i</sub>（e） times,i=1,2,and satisfying the condition that foreach v in Vf（v）≤r<sub>1</sub>（v）=r<sub>2</sub>（v）≤g（v）where r<sub>4</sub>（v） denote the number of the arborescences in G<sub>?</sub> rooted at v.展开更多
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of node...This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.展开更多
基金Work Supported by the exchange program between the Academia Sinica and the Max Planck Society
文摘Let G<sub>1</sub> and G<sub>2</sub> be finite digraphs,both with vertex set V.Suppose that each vertexv of V has nonnegative integers f（v） and g（v） with f（v）≤g（v）,and each arc e of G<sub>4</sub> hasnonnegative integers a<sub>i</sub>（e） and b<sub>i</sub>（e） with a<sub>i</sub>（e）≤b<sub>i</sub>（e）,i=1,2.In this paper we give anecessary and sufficient condition for the existence of k arborescences in G<sub>4</sub> covering each are（?） of G<sub>i</sub> at least a<sub>i</sub>（e） and at most b<sub>i</sub>（e） times,i=1,2,and satisfying the condition that foreach v in Vf（v）≤r<sub>1</sub>（v）=r<sub>2</sub>（v）≤g（v）where r<sub>4</sub>（v） denote the number of the arborescences in G<sub>?</sub> rooted at v.
基金This research is supported by National Natural Science Foundation(70471042)
文摘This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.
