论文部分内容阅读
本文证明了在Metric情况下内点带权的最小生成树问题是NPhard的.给出了一个近似度为3．582的近似算法,并对算法的正确性和近似度进行了详细的分析和证明.本文是关于内点带权的最小生成树问题的第一篇近似算法的文章,其中的恩想和方法对以后有关这方面的工作有重要的理论价值和指导意义.
内点带权的最小生成树的近似算法
【摘 要】
：
本文证明了在Metric情况下内点带权的最小生成树问题是NPhard的.给出了一个近似度为3．582的近似算法,并对算法的正确性和近似度进行了详细的分析和证明.本文是关于内点带权的
【机 构】
：
复旦大学计算机科学与工程系,上海,200433
【出 处】
：
2005年全国理论计算机科学学术年会
【发表日期】
：
2005年期
其他文献
本文基于DCT域DC分量,提出了一种结合人类视觉系统纹理掩蔽特性的自适应水印算法.利用MATLAB对该算法进行了实现,并研究了JPEG压缩、高斯噪声、椒盐噪声、图像剪切等常见图像
5月21日,中国和俄罗斯签署了一项价值4000亿美元的天然气供应协议.习近平主席与普京总统在上海共同见证了签字仪式.rn美国媒体说:“中国签订了一项期盼已久的为期30年的协议,
期刊
本文提出了一种求解带度约束的最小代价组播路由树算法DCMST(Degree-ConstrainedMinimumSteinerTree),运用迭代思想,每次迭代执行两个过程:构建初始可行解和邻域搜索,寻找满
途牛的愿景是成为旅游的入口.上市之后,我们离目标更近了.rn2006年途牛创立之初,就专注于在线休闲旅游的细分市场.当时在线休闲旅游市场几乎是零,线下休闲旅游服务存在着很大
期刊
本文介绍了成本分析理论,并结合自动入侵响应的方法特点,将成本分析理论应用于AAIRS中,构架了一个基于成本分析的自适应入侵响应系统CAIRS,研究了该模型中的分析模块和成本分