论文部分内容阅读
区别于传统对带权最大独立集问题的研究,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性.并且通过对问题结构的研究,给出了一个近似度为1/[△'+1]/3]的近似算法,△′为图中点的最大度数.
边带权最大独立集问题及其近似算法
【摘 要】
：
区别于传统对带权最大独立集问题的研究,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性.并且通过对问题结构的研究,给出了一
【机 构】
：
复旦大学计算机工程系智能信息处理实验室
【出 处】
：
计算机科学
【发表日期】
：
2004年9期
【基金项目】
：
科技部科研项目，国家自然科学基金，上海市科技发展基金
其他文献
由广东科学馆、汕头市科学技术局、汕头市科学技术协会主办，汕头科技馆、汕头市科普教育联盟承办的“人类文明的源与流科普巡展”，于今年3月10日至4月18日先后走进市林百欣科技
几年前，我们还很难把电脑、网络与老人联系在一起。如今，老年人使用电脑、手机在网上冲浪已经不是什么新鲜事。据《第45次中国互联网络发展状况统计报告》显示，截至2020年3月，我国网民规模达9.04亿，手机网民规模达8.97亿，网民中50岁及以上网民群体占比16.9%，人数超1.5亿。这说明互联网正在成为越来越多老年人获取信息、交流沟通、娱乐休闲的新工具、新空间。 但隨着老年网民的增多，确实也出现了
<正> Internet的蓬勃发展正深刻地影响着传统的渠道模式。可以预期,未来电子化的交易途径将使物流、资金流和信息流的应用和管理变得更加容易,一个以Internet为纲的新型渠道
利用X射线衍射及磁测量手段研究了Y2Al3Fe14-xMnx系列化合物的结构.结果表明,该系列化合物具有Th2Ni17型结构;随着x的增加,化合物的单胞体积呈现非线性的变化,这表明在化合物
本文将范例的结构相似性问题提炼为结构图的相似问题,改变了将范例属性线性地映射到区间的方式,建立以关键节点为特征的分层模型,来进行范例结构图比较,并得到一个可以计算的
确定平面点集的凸壳是计算几何中的一个基本问题.一维可重构流水线总线并行机是近年提出的一种采用光连接的并行计算模型.本文在规模为n的可重构流水线总线并行机上提出了一
分布式体系结构已成为高性能路由器普遍采用的实现结构,然而迫切需要解决的问题是如何实现独立于上层软件及底层硬件的通用性支撑软件体系结构.本文针对高性能路由器体系结构