【摘 要】
：
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为最小概率支配集问题.证明最小概率支配集问题
【机 构】
：
华南师范大学计算机学院,广东 广州 510631
论文部分内容阅读
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为最小概率支配集问题.证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法.基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题,得出近似比结果.在真实的社交网络实例上进行实验,结果表明贪心算法所求的概率支配集中节点个数平均占总节点个数的14％～15％.
其他文献
针对传统的脚本建模存在语言机制复杂繁琐、开发效率不高、可靠性难保证、建模阶段和交互阶段相互独立等问题,基于分划与递推(PAR)及其Apla抽象程序设计语言,设计与原Apla语
论述了最近10多年有限自动机重置问题在算法方面的研究进展.首先形式定义一些基本概念和四个有关重置的问题,给出这些问题的计算复杂性结果;然后回顾了2008年前的算法发展历
在总结格密码困难问题发展和求解中关键理论与技术的基础上,从渐进最短向量问题(approx-SVP)入手,对比分析了经典格基约减算法的优缺点,重点研究了其求解推进过程中的关键技
《营养学杂志》刊登的一项最新研究发现,一周吃两个或更多核桃能够降低患Ⅱ型糖尿病的风险。在所有坚果中,核桃抗氧化物质含量最高,并含有丰富的不饱和脂肪酸,已被证明可以改
研究了非确定有限自动机的最短D1-同步字的计算问题.针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于pa
简易食用菌制种新模式湖北省宜昌市四○三里区食用菌研究室工程师胡文华，经过多年探索实践，研究出以城乡菇农家庭为轴心的食用菌家庭菌种场生产技术新模式。运用该模式制菌种，只
中椒６号系由７９－１自交系为母本，８３－５８－１自交系为父本配制而成的辣椒一代杂种。中早熟，一般６６６．７ｍ２产量２５００～５０００ｋｇ，抗病毒病。果实粗牛角形，味微辣，品质优良。平均单果重４５～６２ｇ。耐贮运。已在南菜北运基地及其它省市大面
鸢尾花似蝶展翅张万佛鸢尾花是属于鸢尾科，鸢尾属的植物，同属的约有２００种以上，大部分分布在地球的北温带。花卉大都十分美丽。令提出其中的鸢尾（ｌｒｉｓｔｅｅｔｏｒｕＩｍＭａｘｉｍ）叙述于下：鸢尾，又名蓝蝴蝶，它的花色和形