期刊文章详细信息
最小K度限制树的构建及算法改进
文献类型：期刊文章
机构地区：[1]昆明医科大学海源学院文理系,云南650106 [2]云南师范大学实验中学高中数学组,云南650031
年 份：2015
期 号：3
起止页码：173-174
语 种：中文
收录情况：普通刊
摘 要：结合最小k度限制树和一维装箱这两个问题,本文研究了一个新的最优化问题:给定一个简单的连通无向网络G=(V,E;w)及常数L。我们用长度为"L"的材料构建k度限制树T,且T上的每条边至多能用一次料头(指材料构建完某条边后剩下的部分)。假设所用材料的根数为C,目标是C尽可能小。本论文对所提问题的特殊情形设计了一个3/2近似算法,对一般情形设计了一个2-近似算法,接着将2-近似算法改进到7/4-渐进近似。
关 键 词：网络 构建 k度限制树 NP-难 装箱
分 类 号：TP301.6]
参考文献：
正在载入数据...
二级参考文献：
正在载入数据...
耦合文献：
正在载入数据...
引证文献：
正在载入数据...
二级引证文献：
正在载入数据...
同被引文献：
正在载入数据...
