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

图和网络的连通性分析及其在算法设计中的应用

• 批准号: 17500008
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 2.37万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500008/
• 关键词: Algorithm; Applied Mathematics; Mathematical Engineering; Fundamentals of Informatics; Graph Theory; Network; Approximation Algorithm; Connectivity; ネットワーク設計; 連結度; 最小カット; グラフ分割; グラフの直径; グラフ増大問題

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).

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

项目成果

A fast edge-splitting algorithm in edge-weighted graphs

• DOI: 10.1093/ietfec/e89-a.5.1263
• 发表时间: 2006-05-01
• 期刊: IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
• 影响因子: 0.5
• 作者: Nagamochi, Hiroshi

Approximating the minimax rooted-subtree cover problem

逼近极小极大有根子树覆盖问题

• 发表时间: 2005
• 期刊: IEICE Transactions on Fundamentals of Electro-nics, Communications and Computer Sciences E88-A
• 作者: S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi
• 通讯作者: H. Nagamochi

Packing unit squares in a rectangle

将单位正方形包装在长方形中

• 发表时间: 2005
• 期刊: The Electronic Journal of Combinatorics 12・1
• 作者: S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi;H.Nagamochi;L.Zhao;H.Nagamochi;H.Nagamochi;H.Nagamochi;H.Nagamochi;石井利昌;H.Nagamochi
• 通讯作者: H.Nagamochi

Bisecting a four-connected graph with three resource sets

用三个资源集平分四连通图

• 期刊: Discrete Applied Mathematics (掲載確定)
• 作者: S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi;H.Nagamochi;L.Zhao;H.Nagamochi;H.Nagamochi;H.Nagamochi;H.Nagamochi;石井利昌;H.Nagamochi;H.Nagamochi;H.Nagamochi;Y.Karuno;Y.Kamidoi;H.Nagamochi;H.Nagamochi;T.Ishii
• 通讯作者: T.Ishii

On 2-approximation to the vertex-connectivity in graphs

关于图中顶点连通性的 2 近似

• 发表时间: 2005
• 期刊: Inst.Electron.Inform.Comm.Eng.Trans.Information and Systems E88-D・1
• 作者: Yang D.Y.;Fushimi.H.;Cai S.Q.;Komatsu K.;H.Nagamochi
• 通讯作者: H.Nagamochi