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路割问题，并对每个问题进行了总结。组播树问题：在这项工作中，我们提出了一个(3/2+(4/3)ρ)-近似算法，其中ρ是Steiner树问题的最佳可达近似比。与已知的近似算法中的最佳逼近比(2+ρ)相比，ρ越高，算法的逼近比越高。2.队列布局问题。在这项工作中，我们研究了一类包含几个迄今单独研究的有向图类的重线有向图，并给出了重线有向图排队数的上下界。3.最小k路割问题。在这项工作中，我们定义了一个新的问题，并在新问题的最优解方法的基础上设计了一个求解最小k-路割问题的2-近似算法。利用这一结果，我们将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