|
|||||
|
|
| 关于K棵支撑树的2个问题 | |
| 引用本文： | 王泽磊,张同全,李建平.关于K棵支撑树的2个问题[J].云南大学学报(自然科学版),2004,26(B07):27-28,32. |
| 作者姓名： | 王泽磊 张同全 李建平 |
| 摘 要： | 给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。 |
| 关 键 词： | 最优算法 最小支撑树 k近似 连通图 复杂度 |
| 本文献已被 维普 等数据库收录！ | |