-
题名环上的最大流通量问题
被引量：1
- 1
-
-
作者
陈智斌
李建平
-
机构
云南大学数学系
-
出处
《云南大学学报（自然科学版）》
CAS
CSCD
2004年第4期288-291,共4页
-
基金
国家自然科学基金资助项目(10271103)
云南省自然科学基金资助项目(2003F0015M).
-
文摘
研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,…,n-1},每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对{si,ti}(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点对中的某些点对(也许是所有的),此时每个点对就由一条道路相连,在通过环上每条边的总条数不超过其边整数容量限制的条件下,最大化所用到的道路条数.通过引入单方向概念并应用LP-rounding技巧,证明了环上的单方向最大流通量问题属于P类,即可有多项式时间算法求解,并因此获得了环上最大流通量问题的一个2-近似多项式算法.
-
关键词
环
最大流通量
lp-rounding技巧
近似算法
NP-困难
-
Keywords
lp-rounding technique
approximation algorithm
NP-hard
-
分类号
O153.3
[理学—数学]
-
