限制性网络构建问题的算法设计与复杂性理论研究

Network construction problems generalize network optimization problems and bin-packing problem, come from scientific research and real life, and have great values for theoretical research and wide application area. There have already been some good results for general network construction problems, but nobody has studied in-depth the network construction problems with some restrictions. Therefore, we will add some constraint conditions into some general network construction problems, and then study these constrained network construction problems (the definitions in detail will be provided in the text). Based on the various structures (such as path, spanning tree, arborescence etc.) of graph or digraph, the main research contents of this project include: (1) the restricted shortest path construction problem and its special version; (2) the constrained minimum spanning tree construction problem and its special version; (3) other various constrained network construction problems and their corresponding special versions. First, we will establish some mathematical models that describe these problems, analyze in-depth the characteristics and nature of the various structures of the graph, and master the strategies and algorithm design techniques for solving the corresponding network optimization problems. Then, we will utilize relevant methods of combinatorial optimization theory and graph theory to find some efficient strategies, design some efficient approximation algorithms or asymptotic approximation algorithms to solve these problems, and finally analyze the complexity of algorithms designed. We expect to publish 6-8 research papers with high level.

网络构建问题是网络优化问题和装箱问题的推广形式，其问题模型来源于科学研究和现实生活，具有重要的理论研究价值和广泛的应用领域。对于一般的网络构建问题已经得到了一些好的结果，但是对于带有一些限制条件的网络构建问题还没有人深入研究过，为此，本项目在一般的网络构建问题模型中增加一些限制条件，研究限制性网络构建问题（具体定义见正文），根据图的各种不同结构（如路、支撑树、树形图等），本项目主要研究内容包括：（1）限制性最短路构建问题及其特殊形式；（2）限制性最小支撑树构建问题及其特殊形式；（3）关于其它各种结构的限制性网络构建问题及相应的特殊形式。首先，建立刻画这些问题的数学模型，深入分析图的各种结构的特征和性质，掌握解决相应网络优化问题的策略和算法设计技巧，再利用组合最优化理论、图论的相关方法寻找解决这些问题的策略，设计近似或渐近近似算法解决这些问题，分析其时间复杂性。拟发表6-8篇高质量科研论文。

网络构建问题是网络优化问题和装箱问题的推广形式，其问题模型来源于科学研究和现实生活，具有重要的理论研究价值和广泛的应用领域。本项目对一般的网络构建问题以及增加一些限制条件的限制性网络构建问题做了研究，主要研究内容如下：(1) 一般形式的网络构建问题；(2) 最小支撑树网络构建问题；(3) 单源最短路径树网络构建问题；(4) 限制性最短路构建问题及其特殊形式；(5) 1-线最小斯坦纳树问题及其特殊形式；(6) 1-定直线限制斯坦纳树的斯坦纳点数最小化问题。我们深入分析图的各种结构的特征和性质，掌握解决相应网络优化问题的策略和算法设计技巧，再利用组合最优化理论、图论的相关方法寻找解决这些问题的策略，设计了若干近似或渐近近似算法解决这些问题，并分析它们的时间复杂性。