Analysis of properties on the connectivity of graphs and networks and its applications to design of algorithms

通信网络中的许多问题可以建模为图问题，如果我们固定的几个因素描述的问题。在这项工作中，我们首先建模的通信网络中的问题，图（网络）的问题，通过选择的必要条件，从许多复杂的条件查询的通信问题，然后通过观察问题的结构分析的连通性的性质。此外，我们设计的近似算法使用的数学结构表征的性质，我们阐明。从我们的工作中，得到了许多与图和网络的连通性有关的结果。在下文中，我们将结果大致分为多播树问题、队列布局问题和最小k-way割问题，并对每一个问题进行总结.多播树问题：在这项工作中，我们提出了一个（3/2+（4/3）ρ）-近似算法，其中ρ是Steiner树问题的最佳可实现的近似比。与已有近似算法的最佳近似比（2+ρ）相比，ρ提高得越多，算法的近似比提高得越多. 2.队列布局问题。本文研究了迭代线有向图类，它包含了迄今为止已经研究过的几个有向图类，并给出了迭代线有向图的个数的上界和下界。3.最小k路切割问题在这项工作中，我们定义了一个新的问题，并设计了一个2-近似算法的基础上的最小k路切割问题的最佳解决方案的新问题的方法。利用这个结果，我们将一个2-近似算法的时间复杂度从O（k（mn+n^2logn））改进为O（mn+n^2logn）.

Many problems in communication networks can be modeled as graph problems if we fix several factors describing the problems. In this work, we first modeled problems in communication networks as graph (network) problems by selecting the essential conditions from a lot of complex conditions inquired for the communication problems and then analyzed properties on the connectivity by observing the structures of the problems. Furthermore, we designed approximation algorithms using the mathematical structures characterizing the properties that we elucidated. From our work, many results related to properties on the connectivity of graphs and networks were obtained. In what follows, we classify the results roughly into the multicast tree problem, the queue layout problem, and the minimum k-way cut problem, and then state each summary.1. The multicast tree problem: In this work, we proposed a (3/2+(4/3) ρ)-approximation algorithm for this problem, where ρ is the best achievable approximation ratio for the Steiner tree problem. Compared with the best approximation ratio (2+ρ) in the previously known approximation algorithms, the more ρ is improved, the more the approximation ratio of our algorithm is improved. 2. The queue layout problem. In this work, we studied on the class of iterated line digraphs which contains several digraph classes that were studied individually so far, and present upper and lower bounds on the queuenumber of iterated line digraphs. 3. The minimum k-way cut problem. In this work, we defined a new problem, and designed a 2-approximation algorithm for the minimum k-way cut problem based on a method for the optimum solution for the new problem. Using this result, we improved the time complexity of a 2-approximation algorithm from O(k(mn+n^2logn)) to O(mn+n^2logn).