分散処理に適した計算機網の分割とそのアルゴリズムに関するグラフ理論的研究

计算机网络划分及其适合分布式处理的算法的图论研究

基本信息

批准号：
05680271
负责人：
和田幸一
金额：
$ 1.34万
依托单位：
Nagoya Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

项目摘要

本研究では、計算機網の分割問題を網に対応するグラフG=(V,E)を分散環境に適した条件Cを満足するようにk個の連結なグラフG_1,G_2,...,G_kに分割するものと定義する。条件Cとしては次のようなものを考慮する。(C_v)各Gi(1≦i≦k)がそれぞれ指定された点を含み、指定された個数の点(または辺)を含みそれぞれ点を共有しない。(C_e)各Gi(1≦i≦k)がそれぞれ指定された点を含み、指定された個数の点(または辺)を含みそれぞれ辺を共有しない。いずれも分散環境における耐故障性を考慮している。また、(C_V)、(C_E)において指定された点の条件を取り除いたものを基無指定と呼ぶ。ここではまず、(C_V)条件に対する問題はグラフがk-連結なら解を持つことを示した(文献(1))。また、(C_E)条件に対する問題はグラフがk-辺連結なら解を持つこと、及び基無指定の場合分割数と辺連結度関係を明らかにした(文献(4))。さらに、k=3の場合にはいずれの問題に対しても効率的なアルゴリズムを示した(文献(2))。これらの結果は従来の結果を真に拡張したものになっているだけでなく応用範囲が広く、耐故障性の高い路線割当の効率的な構成に利用できる(文献(3)(6))ことを明らかにした。計算機網に対応するグラフの生成木(全ての点を含む木)を求めることは辺集合の分割と考えることができ、その網に対する効率的な通信はある条件を満たす生成木を用いて行われるが、ここでは与えられた点がその木の中心となるような生成木を求める理論上最も速いアルゴリズムを示した(文献(5))。また、この結果はこの会議において最優秀論文賞を受賞した。

在这项研究中，我们将计算机网络分配问题定义为将与网络相对应的图形g =（v，e）划分为k串联图G_1，g_2，...，g_k，以满足适合分布式环境的条件C。将以下内容视为条件C：（C_V）每个GI（1 i i k）包含指定的点，包含指定的点（或侧面），并且不共享点。（C_E）每个GI（1≦i k）包含指定的点，包含指定的点（或侧面），并且不共享边缘。两者都考虑到分布式环境中的容错。此外，（C_V）中指定点的状态和（C_E）被称为未指定。在这里，我们首先证明（C_V）条件的问题如果图为k concateNated（参考（参考（1）），则具有解决方案。此外，（C_E）条件的问题表明，如果图形是K边连接，则在未指定图表时划分数量和边缘连接程度之间的关系（参考（参考（4））。此外，在K = 3的情况下，这两个问题都显示了有效的算法（参考（参考））。这些结果不仅是传统结果的真正扩展，而且还具有广泛的应用，并且可用于有效地构建途径分配，并具有高功能公差（参考文献（3）（6））。找到与计算机网络相对应的图形生成树（包含所有点的树）可以被视为边缘集的划分，并且使用满足某些条件的生成器进行了有效与网络进行的通信，但是在这里我们已经证明了以下理论：找到生成器的最快算法是找到一个给定点的生成器，其中给定点是树的中心（参考（5））。该结果也在本次会议上赢得了最佳纸张奖。