抗干扰信号传递网络中的若干优化问题研究

Signal transmission networks are widely used in practical applications and our daily life. In order to model the situation that the signal should be anti-interference of each other during the signal transmission in the network, Andrews et al. and Borozan et al. introduced the concepts of proper connection number and strong proper connection number which act as the anti-interference optimization criteria. In this research project, we will study these two optimization criteria and mainly focus on the following three problems: First, we will address the computational complexity of proper connection number problem of graphs, and in the case of NP-hardness, construct polynomial-time 3/2-approximation algorithm for computing the proper connection number of graphs. Moreover, we will characterize bipartite graphs with strong proper connection number 2. Second, we will prove the NP-hardness of the optimal proper connected k-edge coloring problem, and present polynomial-time algorithms for the optimal proper connected k-edge coloring problem of a given tree and the optimal proper connected 2-edge coloring problem of a given graph, respectively. Third, we will establish the optimal routing model in the weighted anti-interference signal transmission networks, and for the cases of non-negative weights and conservative weights, we will present polynomial-time algorithms.

信号传递网络广泛存在于实际应用和人们的日常生活当中。Andrews等人和Borozan等人将一类抗干扰信号传递网络转化为图论模型并提出了图的正常连通数和强正常连通数这两个抗干扰优化指标。本项目拟对这两个优化指标及相关问题进行研究，重点研究以下三个问题：一、解决一般图正常连通数问题的计算复杂性，并在该问题是NP-困难的前提下给出计算图的正常连通数的多项式时间3/2-近似算法。此外，对强正常连通数等于2的二部图类进行完全的刻画。二、证明最优正常连通k-边染色问题的NP-困难性，构造多项式时间算法解决树的最优正常连通k-边染色问题及一般图的最优正常连通2-边染色问题。三、建立加权抗干扰信号传递网络中的最优路由模型，并对最优路由问题在权重非负、权重保守等假设下给出多项式时间算法。

抗干扰信号传递网络广泛存在于实际应用和人们的日常生活当中。Andrews等人和Borozan等人将一类抗干扰信号传递网络转化为图论模型，利用图的染色及着色图相关理论和方法对该模型进行研究，吸引了大量研究者的关注，进而形成了图论中的一个热点课题。本项目对图的染色及着色图相关问题开展了两方面深入的研究。第一：图的染色问题：即给定一个图，想要找到使得该图满足一定性质的染色方案。第二：边着色图中特定子图的存在性问题：即在给定的边着色图中寻找满足某些条件的子图。受本项目资助，共发表SCI论文8篇。本项目的代表性成果如下（1）对子式k可着色图的开邻域无冲突色数问题进行了研究，并利用该结果成功解决了前人提出的两个问题（2）对图的强正常连通数的计算复杂性进行了研究，证明了判定一个三正则图是否是3-SPC的问题是NP-完全的。刻画了2-SPC三正则图的强迫分支的结构，并且进一步对2-SPC三正则图进行了完全的刻画。（3）证明了Fujita和Magnant于2011年提出了的猜想“对每一个顶点数n大于等于3的边着色完全图，如果它的最小色度大于等于（n+1)/2，那么这个图具有正常点泛圈性”在边着色完全图不含单色三角形的条件下是成立的。