Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）
数学与计算机科学     
约束最小生成树问题研究
浙江大学玉泉校区高等数学研究所，浙江 杭州 310027
Study on the Problem of Constrained Minimum Spanning Tree
Institute of Advanced Mathematics, Zhejiang University, Hangzhou 310027，China)
 全文: PDF(43 KB)  
摘要： 本文对约束最小生成树问题提出一个算法，它的计算复杂性是O(n3)．然后把约束最小生成树作为约束Steiner最小树的一个近似解，则近似解的性能比为3?/2．
关键词： 生成树;  Steiner树;  近似算法;  性能比     
Abstract: in this paper,an O(n3) algorithm for the constrained minimum spanning tree problem is presented.As an approximation of the constrained Steiner tree problem, this algorithm has a worst-case ratio 3?/2.
Key words: spanning tree    Steiner tree    approximation algorith    worst-case ratim
收稿日期: 1997-01-17 出版日期: 2017-11-10
CLC:  O157  
基金资助: 国家自然科学基金资助项目(19801032)
作者简介: 陈光亭(1965-)，男，现为杭州电子工学院副教授，主要从事组合优化， Steiner树问题及图论等方面研究．
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
陈光亭
张国川

引用本文:

陈光亭，张国川. 约束最小生成树问题研究[J]. 浙江大学学报（理学版）, .

CHEN Guang-ting，ZHANG Guo-chuan . Study on the Problem of Constrained Minimum Spanning Tree. Journal of Zhejiang University (Science Edition), .

链接本文:

https://www.zjujournals.com/sci/CN/    或    https://www.zjujournals.com/sci/CN/Y1999/V26/I2/28

[1] 华荣伟,潘虹,严甜海. 可移动周期性维护排序问题的算法研究[J]. 浙江大学学报（理学版）, 2023, 50(3): 303-309.
[2] 王康, 吴文明, 刘利刚. 三维迷宫的设计与建模[J]. 浙江大学学报（理学版）, 2017, 44(2): 127-133.
[3] 曾志, 刘仁义, 杜震洪, 张丰. 云格环境下基于P2P的动态资源发现机制[J]. 浙江大学学报（理学版）, 2013, 40(4): 463-468.
[4] 苏中根. 经典组合优化问题的概率极限定理[J]. 浙江大学学报（理学版）, 2000, 27(6): 700-713.
[5] 沈灏. 底为正方形的三维装箱问题[J]. 浙江大学学报（理学版）, 1999, 26(3): 44-51.