论文部分内容阅读
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问题中的其他相关问题进一步研究的一些工作。