论文摘要
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问题中的其他相关问题进一步研究的一些工作。
论文目录
相关论文文献
- [1].Harmony search optimization applied to reservoir engineering assisted history matching[J]. Petroleum Exploration and Development 2020(01)
- [2].Research on nonlinear model predictive control for turboshaft engines based on double engines torques matching[J]. Chinese Journal of Aeronautics 2020(02)
- [3].Satellite Image Matching Method Based on Deep Convolutional Neural Network[J]. Journal of Geodesy and Geoinformation Science 2019(02)
- [4].A method for matching response spectra of endurance time excitations via the Fourier transform[J]. Earthquake Engineering and Engineering Vibration 2020(03)
- [5].Non-collinear phase-matching sum-frequency generation based on boundary total reflection in bulk KDP[J]. Chinese Optics Letters 2019(08)
- [6].Broadband quasi-phase matching in a MgO:PPLN thin film[J]. Photonics Research 2018(10)
- [7].Toward high efficiency for content-based multiattribute event matching via hybrid methods[J]. Science China(Information Sciences) 2016(02)
- [8].Inexact graph matching using a hierarchy of matching processes[J]. Computational Visual Media 2015(04)
- [9].Image matching algorithm based on SIFT using color and exposure information[J]. Journal of Systems Engineering and Electronics 2016(03)
- [10].A novel method for multi-angle SAR image matching[J]. Chinese Journal of Aeronautics 2015(01)
- [11].A stereo matching algorithm based on SIFT feature and homography matrix[J]. Optoelectronics Letters 2015(05)
- [12].Stable haptic interaction based on adaptive hierarchical shape matching[J]. Computational Visual Media 2015(03)
- [13].Program Optimization of Parametric Matching Design of Central Region Inflector in Cyclotron[J]. Annual Report of China Institute of Atomic Energy 2016(00)
- [14].New event detection based on sorted subtopic matching algorithm[J]. Journal of Chongqing University(English Edition) 2013(04)
- [15].Robotic-vs laparoscopic-assisted proctectomy for locally advanced rectal cancer based on propensity score matching: Short-term outcomes at a colorectal center in China[J]. World Journal of Gastrointestinal Oncology 2020(04)
- [16].Graph-matching-based character recognition for Chinese seal images[J]. Science China(Information Sciences) 2019(09)
- [17].关于路与圈的匹配多项式的一个注记（英文）[J]. 数学季刊(英文版) 2018(02)
- [18].Infrared small moving target detection method based on graph matching[J]. Chinese Optics Letters 2014(12)
- [19].Position optimization of particular solution sources for distributed source boundary point method by volume velocity-matching[J]. Chinese Journal of Acoustics 2015(02)
- [20].Assessment of the accuracy of real-time continuous glucose monitoring system and its correlated factors[J]. China Medical Abstracts(Internal Medicine) 2014(01)
- [21].Displacement residual based DDM matching algorithm[J]. Science China(Information Sciences) 2012(09)
- [22].A reliable algorithm for image matching based on SIFT[J]. Journal of Harbin Institute of Technology 2012(04)
- [23].Automatic Web services composition algorithm based on optimal matching[J]. Journal of Central South University of Technology 2011(04)
- [24].A stochastic policy search model for matching behavior[J]. Science China(Information Sciences) 2011(07)
- [25].A hybrid matching method for geospatial services in a composition-oriented environment[J]. Science China(Technological Sciences) 2010(S1)
- [26].Video Image Block-matching Motion Estimation Algorithm Based on Two-step Search[J]. Journal of Measurement Science and Instrumentation 2010(03)
- [27].General forms of elastic-plastic matching equations for mode-Ⅲ cracks near crack line[J]. Applied Mathematics and Mechanics(English Edition) 2009(05)
- [28].Improved block matching approach to fast disparity estimation[J]. Journal of Systems Engineering and Electronics 2009(06)
- [29].Spectral feature matching based on partial least squares[J]. Chinese Optics Letters 2009(03)
- [30].An optimization model of parameter matching for aircraft catapult launch[J]. Chinese Journal of Aeronautics 2020(01)