图的p-中心、控制集及核的理论与算法

图的p-中心、控制集和核是图论中三个密切相关的重要优化问题，都可归属于"选址问题"，具有重要的理论意义和广泛的应用前景。本项目的研究涉及到图论、组合最优化、选址科学与网络理论，是跨学科的交叉项目。本项目侧重从算法角度研究上述三个问题，研究方法有创新。p-中心问题是选址科学的核心问题之一，控制集在设计p-中心问题的近似算法时起着重要作用，它也是图论近三十年来发展最快的领域之一，而核问题是图的独立控制集问题在有向图上的推广，在完美图猜想和List染色猜想的研究中有着重要的作用。本项目研究内容主要有：p-中心问题的近似算法及其在特殊网络上的多项式算法；图的电力控制数、配对控制数的估界及其在特殊图类上的多项式算法；有向图k-核的存在性、特定结构网络的吸收数以及核在染色理论中的应用；函数控制数和其它控制参数的估界与极值图的刻画。本项目的研究将推进图论、组合最优化、选址科学及网络理论的交叉研究。