Studies of Graph-Structural Properties on Fault-Tolerance of Networks and Design of Improved Algorithms.

网络容错性的图结构特性研究及改进算法设计。

• 批准号: 21500017
• 负责人: HASUNUMA Toru
• 金额: $ 1.75万
• 依托单位: The University of Tokushima
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500017/
• 关键词: グラフ; ネットワーク; アルゴリズム; 耐故障性

(1) We show that there are two completely independent spanning trees in the Cartesian product of 2-connected graphs. Also, we determine the(h, k)-domination number of an iterated line digraph.(2) We improve upper and lower bounds on the minimum size of a fault-tolerant gossip graph.(3) We design a linear time algorithm for computing the L(2, 1)-labeling number of a tree. Besides, we present tight upper and lower bounds on the(p, q)-total labeling number of a tree and a tight upper bound on the(2, 1)-total labeling number of an outerplanar graph.(4) We design a linear time algorithm for computing the queue-number of a maximal outerplanar graph.

(1)证明了在2连通图的笛卡尔积中存在两个完全独立的生成树。同时，我们确定了迭代的有向图的（h, k）支配数。(2)改进了容错八卦图最小大小的上界和下界。(3)设计了一种计算树的L（2,1）标记数的线性时间算法。此外，我们给出了树的(p, q)-总标记数的紧上界和下界，以及外平面图的(2,1)-总标记数的紧上界。(4)设计了一种计算最大外平面图排队数的线性时间算法。

项目成果

Completely independent spanning trees in torus networks

• DOI: 10.1002/net.20460
• 发表时间: 2012-08
• 期刊: Networks
• 影响因子: 2.1
• 作者: Toru Hasunuma;Chie Morisaka

Improved bounds for miniraum fault-tolerant gossip graphs

改进了最小容错八卦图的界限

• 发表时间: 2011
• 作者: Hasumima T;et al
• 通讯作者: et al

A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs

• DOI: 10.1016/j.jda.2011.12.020
• 发表时间: 2009-11
• 期刊: J. Discrete Algorithms
• 作者: Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno

The (p, q)-total Labeling Problem for Trees

• DOI: 10.1007/978-3-642-17514-5_5
• 发表时间: 2010-12
• 作者: Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno

The (p, q)-total labeling problem for trees

树的 (p, q)-总标记问题

• DOI: 10.1016/j.disc.2012.01.007
• 发表时间: 2012
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Toru Hasunuma;Toshimasa Ishii;Hirotaka Ono;Yushi Uno
• 通讯作者: Yushi Uno