全一问题的最优解及相关问题的算法与复杂性研究

研究图的最小全一问题及相关问题的解的算法与复杂性和近似算法。对于树的全一问题的解的个数给出计数公式；寻求树的最小全一问题的最优解的多项式时间算法；对于二部图，确定其最小全一问题的最优解的算法是否NP-完备的，如果是，找到好的近似算法。对于一般图的全一问题的解，找到一个多项式时间的图论算法。对于一般图的最小全一这个NP-完备问题，寻找好的近似算法以得到好的近似解。对于全一问题的一些变形情况，探讨它们的全一问题和最小全一问题的解的存在性、算法与复杂性、以及近似算法等。对于有向图及其他自动机问题、最小权的自动机问题探讨其最优解的算法与近似算法。本项目的研究不仅具有很强的应用背景，而且具有大量而又挑战性的问题，对于它们的研究具有重要的理论意义。另外，在去年结束的北京国际数学家大会上，有一个大会报告和几个邀请报告都是有关组合优化和NP-完备问题及其近似算法的，因此本项目属于国际数学研究的主流方向。