著者

白楽強 Peter 山川 榎原 博之 中野 秀男

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1994, no.82, pp.89-96, 1994-09-21

被引用文献数

1

---

arrangement graphはstar graphを一般化したグラフであり、star graph同様の良い性質を持っている。さらに、次数、直径、ノード数の点でより柔軟性のある設計ができる。この論文はarrangement graphについて最適なone?to?all放送アルゴリズムを提案する。このアルゴリズムはグラフの階層的な構造を活用して再帰的に実行し、最適なステップ数O()ですべての(!)/((?)!)プロセッサにメッセージを放送することができる。A new interconnection network topology-the arrangement graph, as a generalization of the star graph topology, possesses excellent topology like the star graph and presents more flexibility than the star graph in terms of choosing the major design parameters: degree, diameter, and the number of nodes. In this paper, we propose an optimal distributed algorithm for one-to-all broadcasting on the arrangement graph in fault free mode. The algorithm, which exploits the rich inherent structure of the graph to constitute the structure of broadcasting binary tree and works recursively, broadcasts a message to all the (n!)/((n-k)!) processors in O(klgn) steps.