数学物理学报(英文版)

• 论文 • 上一篇    下一篇

ON THE BOTTLENECK CAPACITY EXPANSION PROBLEMS ON NETWORKS

杨超; 张建中   

  1. 华中科技大学管理学院, 武汉 430074
  • 收稿日期:2003-11-03 修回日期:2004-08-10 出版日期:2006-04-20 发布日期:2006-04-20
  • 通讯作者: 杨超
  • 基金资助:

    This research is supported by National Natural Science Foundation(70471042)

ON THE BOTTLENECK CAPACITY EXPANSION PROBLEMS ON NETWORKS

Yang Chao; Zhang Jianzhong   

  1. College of Management, Huazhong University of Science and Technology, Wuhan 430074, China
  • Received:2003-11-03 Revised:2004-08-10 Online:2006-04-20 Published:2006-04-20
  • Contact: Yang Chao

摘要:

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,\overline{C})$ consisting of
a set of nodes V={v1,v2,... ,vn}, a set of arcs $A \subseteq \{(v_i,v_j)\ |\ i=1,2,\cdots ,n; ~j=1,2,\cdots ,n \}$ and a capacity vector $\overline{C}$. The component $\overline{c}_{ij}$ of $\overline{C}$ is the capacity of arc $(v_i,v_j)$. Define the capacity of a subset $A'$ of $A$ as the minimum capacity of the arcs in $A$, the capacity of a family ${\cal 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 $(v_i,v_j)$ is $w_{ij}$. In the node-expanding model, it is
assumed that the capacities of all arcs $(v_i,v_j)$ 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.

关键词: Networks and graphs, maximum capacity, spanning arborescence,
polynomial algorithm

Abstract:

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,\overline{C})$ consisting of
a set of nodes V={v1,v2,... ,vn}, a set of arcs $A \subseteq \{(v_i,v_j)\ |\ i=1,2,\cdots ,n; ~j=1,2,\cdots ,n \}$ and a capacity vector $\overline{C}$. The component $\overline{c}_{ij}$ of $\overline{C}$ is the capacity of arc $(v_i,v_j)$. Define the capacity of a subset $A'$ of $A$ as the minimum capacity of the arcs in $A$, the capacity of a family ${\cal 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 $(v_i,v_j)$ is $w_{ij}$. In the node-expanding model, it is
assumed that the capacities of all arcs $(v_i,v_j)$ 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.

Key words: Networks and graphs, maximum capacity, spanning arborescence,
polynomial algorithm

中图分类号: 

  • 90C