Matching和packing问题的参数算法研究

来源 :中南大学 | 被引量 : 0次 | 上传用户:wooicheang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Matching Problem(图的匹配问题)和packing问题都是一类重要的NP难问题。3-维匹配问题和P2-packing问题是两个具有代表性的matching和packing问题。在参数复杂性理论框架内,人们对3-维匹配问题和P2-packing问题的参数算法已作出了大量的研究。本文主要从参数复杂性角度针对3-维匹配问题和P2-packing问题的核心化及参数算法展开研究。本文首先介绍了核心化技术,并阐述了核心化在点覆盖问题和3-维匹配问题的具体应用。同时提出了一个改进的3-维匹配问题的核心化算法,从而将问题的核降低到6k3-12k2+6k。在3-维匹配问题的参数算法研究中,着色和动态规划是解决该问题的主要技术。本文通过对问题结构的深入分析,总结出关于k+1大小的匹配和k大小的匹配之间的符号包含关系,同时利用了J.Chen等人的关于完全散列函数的新的着色理论,从而获得了一个算法运行时间为O*(3.423k)的确定型参数算法,大大改进了目前关于3-维匹配问题最好的运行时间为O*(163k)的确定型参数算法。在P2-packing问题的参数算法研究中,基于对问题结构的深入分析,本文提出了一个新的核心化算法,算法对图中的点作出进一步的优化处理,从而将问题的核降低到7k,由此得到一个时间复杂度为O*(24.142k)的参数算法。本文最后对3-维匹配问题和P2-packing问题的参数算法研究工作进行了总结,并阐述了将来对matching和packing问题中的其他相关问题进一步研究的一些工作。
其他文献
自从1987年Yablonovitch和John各自独立的提出“光子晶体”这一新概念以来,光子带隙结构(Photonic Bandgap,简称PBG)在微波与毫米波集成电路的应用越来越成为研究热点。目前,国
NP-完全理论是算法研究方面的重要的基本理论,它在计算机、电气工程和运筹学方面都有重要的地位。本文主要以算法技巧为着眼点来研究此类问题,希望在解决方式上有新的突破。加
互联网技术的进步和电子商务的快速发展要求在构建新企业应用的时候,新构建的应用既能够方便地与企业现存的各种遗留系统进行通信,又能够方便地与将来的系统进行通信。以此为
随着网络技术的飞速发展,软件产业的不断进步,企业对计算机技术依赖程度越来越高。软件也从单机的软件工具,发展为分布式,网络化,集信息自动化、数据存储、企业管理、企业策划等越
近年来,随着企业对计算要求的不断提高,计算机应用系统开始由集中式向分布式发展。软件的体系结构也从C/S模式转向了多层应用体系结构。以工业故障诊断系统为例,在很多工业故障诊
市场经济中,开展上市公司业绩评价在理论、实践上均具有重要作用。无论是对政府转变职能和加强宏观调控,还是对公司改善经营管理,以及投资者及时调整投资决策,都有十分重要的意义
便携式媒体播放器(PMP)是今年被讨论最多的一个话题。PMP播放器的优点很多,它能够直接播放高品质视频、音频,也可以浏览图片以及作为移动硬盘、数字银行使用,更有产品还具备一些
本文以电子政务应用为背景,研究了基于XML的异构数据交换技术和文本自动分类技术。重点研究了关系数据库模式到XML模式的映射以及XML的关系数据库存储技术。通过基于用户请求
随着计算机技术的高速发展,人类社会已经进入一个信息资源大爆炸的时代,分布式文件系统已经成为存储和管理海量信息的最佳选择。为了保证分布式文件系统可以正常有效的运行,避免
随着低功耗无线通信技术、微电子技术、微型传感器等技术的发展,使得能够在微小传感器内集成信息采集、数据处理和无线通信等多种功能。无线传感器网络是由大量的传感器节点组