团分划问题的确定参数算法

来源 :复旦大学 | 被引量 : 0次 | 上传用户:asfdasdfasd
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
团分划问题的目标为将给定图分划为给定大小的完全图集合。在计算生物学的聚类分析等中有着广泛的实际应用场合,团分划问题属于NP-完全问题,因此除非P=NP成立,我们很难找出一个较快得到精确解的算法。确定参数算法在上个世纪90年代被提出.作为算法理论中的新兴研究领域,它是解决一部分NP-完全问题的有效途径。本文对团分划问题的确定参数算法进行了研究,在适用于K4-free图的Mujuni算法的基础上做出了改进,提出了针对K4-free图的新归约法则。同时分别在K4-free,K4-free平面图,三次图以及平面图的情况下给出了时间复杂度更好的确定参数算法。此外,我们通过实验数据显示确定参数算法及新的归约法则在解决这一问题上的优势所在,从而为团分划算法在一般图情况下时间复杂度的改进打下了理论基础。
其他文献
随着信息技术广泛应用,用户产生的各种信息越来越多,而数据库作为存储用户数据的场所,存储了大量和用户隐私相关的数据。传统的访问控制因为模型本身存在的弊端,可能导致用户
使用Deep Web集成系统获取隐藏在数据库中的高质量数据成为人们获取信息的重要途径之一。由于Deep Web集成系统查询信息时需从Web上海量的数据源获取信息,因而系统获取信息所
从1988年Morris蠕虫爆发后,互联网一直遭受网络蠕虫的威胁。网络已渗透到国家安全、经济、生活等领域,网络蠕虫对互联网的威胁日益增大。P2P蠕虫利用P2P网络的拓扑结构,可以
近年来,随着计算机应用在不同领域发展的深入,相应的系统要求的差异性也越来越大,这种趋势对于可定制芯片的兴起起到了极大的促进作用。在众多系统芯片开发流程和方法当中,软
随着使用ARM核心处理器作为解决方案的嵌入式智能产品越来越多,基于ARM核心处理器的嵌入式软件调试方法,在开发过程中日益受到人们的关注。ARM公司新近推出的ARM11核心处理器
随着互联网的飞速发展,各种新应用不断涌现,用户数量急剧增加,网络流量呈现爆炸式的增长,网络拥塞问题变得越来越严重。网络发生拥塞会导致吞吐量急剧下降、数据包大量丢失以
随着软件和网络应用的迅速发展,数据库的应用越来越广泛,发挥的作用也越来越重要,数据库管理系统已经成为企业的核心IT系统,大数据量、高并发度也越来越成为企业业务处理系统的首
在网络安全通信问题中,抵御拜占庭攻击越来越受到广大科研究工作者的关注,并且成为当前研究的热点问题。当网络中存在这种攻击时,攻击者不仅想得到一些有用的消息,还想通过多
随着信息科技的快速发展,人类的生活发生了翻天覆地的变化。通过智能科学在生活中的普遍应用,人们可以随时享受智能科学带来的方便和快捷。在智能科学中,最具有代表性的就是机器
H.264是一种高性能的视频编码方法,但其在运动估计、帧内预测、插值、变换和算术编码等方面具有很高的计算复杂度。根据其内在的并行度,通过分析并行化的瓶颈所在,合理地设计