著者

温井 康介 上嶋 章宏

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.23, pp.129-136, 2007-03-09

参考文献数

15

被引用文献数

1

---

パズルやゲームの面白さの源は,それらの持つ根源的な難しさにあり,これまで数多くのパズルやゲームの計算複雑さが解析されている.本稿では,ペンシルパズルの一種であるスリザーリンクの盤面を正k角格子状に一般化した,k‐スリザーリンクを提案し,k‐スリザーリンクの解の存在判定を問う問題のNP完全性を,制限付きハミルトン閉路問題からの多項式時間還元を用いて証明する.また,別解問題(ASP,Another Solution Problem,問題例とその1つの解が与えられたとき,他の解の有無を判定する問題)についても考察し,k‐スリザーリンクの別解問題について,そのNP完全性を示す.A fundamental difficulty to solve games and puzzles seems to become the basis for interest factors of them, and the computational complexity of puzzle games have been investigated. This paper proposes k-Slither Link Puzzle, which is a generalization of the traditional Slither Link Puzzle concerning the grids. The puzzle is one of many popular pencil-and-paper puzzles on rectangular grids k = 4, we deal with the puzzles on all the rest of regular tessellations of the plane, i.e. triangular k = 3 and hexagonal grids k = 6. This paper presents the NP-completeness of k-Slither Link Puzzle for k = 3, 6.Moreover, the NP-completeness of ANOTHER SOLUTION PROBLEMS (ASP), which are problems to decide if there is some solution other than a given solution, of the puzzles is proved in this paper.

著者

八登 崇之

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.84, pp.25-31, 2000-09-21

被引用文献数

3

---

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.For many of the widely played games and puzzles, their computational complexities have been analyzed. In this paper, we consider a sort of puzzle "Slither Link" and prove that the problem which determines whether or not a given instance of puzzle has any solutions is NP-complete, by using a polynomial time reduction from the Hamilton Path Problem with respect to restricted graphs. In addition we consider Another Solution Problem for the puzzle, the problem which determines, for a given instance and its solution, whether there is another solution for the instance. We provide a strategy to prove its NP-completeness.

著者

上原 隆平 寺本 幸生

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.2006, no.71, pp.59-64, 2006-07-03

---

折り紙は伝統的な紙工芸であるが,近年,科学としての認知が高まり,数学的な研究が進められている.本論文ではもう一つの伝統的な紙工芸である,飛び出す絵本を取り上げる.飛び出す絵本をデザインする問題を定式化し,その複雑さを議論する.そして本を閉じる問題も,本を開く問題も,ともにNP困難であることを示す.Origami is the centuries-old art of folding paper, and recently, it is investigated as science. In this paper, another hundreds-old art of folding paper, a pop-up book, is studied. A model for the pop-up book design problem is given,and its complexity is investigated. We show that both of the opening book problem and the closing book problem are NP-hard.

著者

八登 崇之

雑誌

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

巻号頁・発行日

vol.2000, no.84(2000-AL-074), pp.25-31, 2000-09-21

---

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.

著者

鴨 浩靖 河邑紀子

出版者

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

雑誌

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

巻号頁・発行日

vol.1996, no.100, pp.1-8, 1996-10-17

---

Koch曲線はEuclid平面上の典型的な自己相似集合として知られている.Koch島はKoch曲線の三つのコピーで囲まれる閉集合である。これらをを計算可能性の観点から調べる.本論文では,古典的計算可能性解析の応用として,Euclid空間上の曲線の計算可能性と閉集合の計算可能性を定義し,Koch曲線は計算可能な曲線であり,Koch曲線もKoch島も計算可能な閉集合であることを示す.Koch curve is known as a typical self-similar set on Euclidean plane. Kochi island is a closed set surrounded by three copies of Koch curve. We investigate them from the viewpoint of computability. In this paper, we define computability of a curve and that of a closed set as an application of classical computable analisys to Euclidean spaces and show that Koch curve is a computable curve and both Koch curve and Koch island are computable closed sets.

著者

浅野 泰仁 今井 浩

雑誌

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

巻号頁・発行日

vol.1998, no.41(1998-AL-062), pp.1-8, 1998-05-20

---

単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。

著者

浅野 泰仁 今井 浩

出版者

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

雑誌

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

巻号頁・発行日

vol.1998, no.41, pp.1-8, 1998-05-20

参考文献数

6

---

単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。SSSP is one of the well known classic problems in graph theory and Dijkstra's algorithm for SSSP is also quite popular. Several improvements of Dijkstra's algorithm have been studied, however, they could not accomplish a linear-time owing to its sorting bottleneck. In 1997, M.Thorup proposed a linear-time algorithm for the SSSP on undirected and integer edge weight graph. However, we can not implement this algorithm naively on computers today since the data structures used in the algorithm need a word of huge length. We propose modifications to implement Thorup's algorithm and implement this algorithm. Moreover, compare execution times of the implementation and famous algorithms.

著者

柳井 孝介 伊庭 斉志

雑誌

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

巻号頁・発行日

vol.2005, no.26(2004-AL-100), pp.1-8, 2005-03-17

---

本稿ではNo Free Lunch Treorem (NFL)の別証明を与える.NFL は「どんな問題に対しても平均的に効率良く解けるような探索アルゴリズムは存在しない」ということを主張する定理であり,探索アルゴリズムあるいは最適化法の研究に大きな影響を与えた.本稿では,より簡潔でかつ直観的な証明を与える.我々は評価関数の空間を部分集合に分割し,それぞれの部分集合ごとにパフォーマンスが得られる確率を合計する.関数空間の分割により,定理のより深い理解が可能となり,またアルゴリズムと問題の関係が明確となる.

著者

牧野 和久 高畑 貴志 藤重 悟

雑誌

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

巻号頁・発行日

vol.2001, no.115(2001-AL-081), pp.27-34, 2001-11-27

---

本論文では,△-正則2 部グラフに対する完全マッチング問題を考察する.ただし,グラフG は,n 節点,m 枝,すなわち,1/2 n △=m とする.我々は,まず,Gabow の方法に基づく新しい単純なO(m log n )アルゴリズムを与える.次に,Cole とHopcroft が提案した正則2 部グラフに対する辺疎化手法を取り入れることにより,そのアルゴリズムをO(m +n log n log △)に改善する.我々のアルゴリズムは,動的木やスプレイ木などの高度なデータ構造を必要としない.

著者

徳丸 雄一 藤原 暁宏

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.23, pp.25-32, 2007-03-09

参考文献数

20

---

本研究では DNA計算を用いて浮動小数点数の演算を行うアルゴリズムを提案する. まずはじめに DNAによる浮動小数点表現を定義する. 本研究で取り扱う浮動小数点数は符号部 指数部 仮数部から構成され 符号部は1ビットの2進数であり また 指数部と仮数部は それぞれqビットとmビットの2進数であるものとする. 次に 浮動小数点数対に対して加算を行う2つのアルゴリズムを提案する. 1つ目のアルゴリズムはO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能であり 2つ目のアルゴリズムはO(m^{2}2^{m})種類のDNAを用いることによりO(1)ステップで実行可能である. また O(n)個の対に対する浮動小数点数の加算を行うアルゴリズムも提案する. このアルゴリズムは O(nm^{2}2^{m})種類のDNAを用いることにより O(1)ステップで実行可能である. また最後に 浮動小数点数の乗算を行うアルゴリズムを提案する. このアルゴリズムO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能である.In this paper, we consider procedures for floating point arithmeticoperations with DNA molecules. We first propose data structure for representing floating point numbers with DNA molecules. The floatingpoint number consists of a sign bit, an exponent and a mantissa. We assume that the exponent and the mantissa are binary numbers of q andm bits, respectively. We next propose two procedures for an addition of floating point numbers. The first procedure executes an addition inO(log m) steps using O(m^{2}) DNA strands, and the second procedure executes an addition in O(1) steps using O(m^{2}2^{m}) DNA strands. Wealso propose a procedure for additions of O(n) pairs of two floating point numbers. The procedure executes O(n) additions simultaneously inO(1) steps using O(nm^{2}2^{m}) DNA strands. We finally propose a procedure for a multiplication of a pair of two floating pointnumbers. The procedure executes a multiplication in O(log m) steps using O(m^{2}) DNA strands.

著者

宇野 毅明

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.93, pp.33-40, 2001-09-25

参考文献数

7

被引用文献数

1

---

議会においては 各党が保有する議席数 法案決定に必要な賛成の票数によって 各党の発言力は変化する. その発言力を数理的なモデルを用いて表現したものが投票力指数である. いくつかのモデルが提案されており それぞれについて その指数を計算するアルゴリズムが研究されている. 本稿では これらのアルゴリズムの改良方法を示し 1つの党の指数計算と同じ計算量で すべての党の指数を計算するアルゴリズムを提案する.In a council, the power of parties changes as the number of persons in the parties, and the number of votes to win. Power indices are indices representing power of parties in the mathematical way by using mathematical models. There proposed several models, and algorithms for computing indices for these models. In this paper, we propose an improvement for these algorithms, and propose improved algorithms for computing indices of all parties running in the time for computing indices of constant number of parties.

著者

宇野 美由紀 河野 智治 加納 幹雄

出版者

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

雑誌

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

巻号頁・発行日

vol.2008, no.6, pp.31-38, 2008-01-23

---

平面格子上にある赤点の集合と青点の集合の分割について述べる.最初の定理は,ハム・サンドイッチの定理と類似する次の結果である.平面格子上にある2n個の赤点と2m個の青点に対して,これらを同時に2等分割する準直交分割が存在する.格子上の点集合において,各格子線上に高々1点しかその点がないとき,この点集合は一般の位置にあるという.また,各格子線との共通部分がひとつの直線分かまたは空集合となる連結領域を格子凸領域という.次に,一般の位置にある赤点集合と青点集合は凸領域によって3等分割できることも示す.つまり,平面格子上の一般の位置にある3n個の赤点と3m個の青点は,平面を3個の格子凸領域に分割して,各領域には赤点n個と青点m個が存在するようにできる.We consider balanced subdivision of red points and blue points in the plane lattice. We first show that if 2n red points and 2m blue points are given in the plane lattice, then there exists a semi-rectangular that bisects both red points and blue points. A set S of points in the plance lattices is said to be in general position if every lattice line contains at most one point of S. For a connected region of the lattice, if the intersection of every lattice line and the region is empty or consists of one line segment, then the region is called a lattice convex set. We next show that if 3n red points and 3m blue points are given in the plane lattice in general position, then the plance can be patitioned into three lattice convex regions so that each region contains exactly m red points and n blue points.

著者

加納 幹雄 佐々木 哲也 藤田 宏明 星 誠司

出版者

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

雑誌

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

巻号頁・発行日

vol.1994, no.11, pp.9-16, 1994-01-25

被引用文献数

2

---

ライフゲーム(fe ga)は平面を格子に分割し、この格子のいくつかに石を置き、これを決まった規則で次々に変化させ、その生物の生死を連想させる石の配置の変化を楽しむゲームである。ここ.ではこれを次のように3つの観点から一般化する。.これにより元のライフゲームとはかなり違う動きをする興味深い新しいライフゲームがいくつか見つかった。()平面は合同な3、5、6角形に分割することもできる。これらの分割においても同様なゲームができる。()4角形の格子分割においても、また他の分割においても、各セルにおいてこれに隣接するセルにはいくつか接し方がある。接し方によって異なる影響を与えるとしてセルの受ける影響を評価する。()ある、ないの2状態から、ない、子、親の3状態があるとしてゲームのルールを定める。Life game can be generalized by combining the following three new ways: (i) The plane can be partitioned into not only squares but also triangles, quadrilateral, pentagons and hexagons. We play new life games on these partitions. (ii) Suppose that the plane is partitioned into n-gons. Then we call each n-gon a cell. For every cell C, some cells D touch C in several ways. So we estimated influence upon C from the touching cells under the assumption that the infuence of D depends on how to touch C. These new estimation give us new life games, at any time each cell is child, adult or dead. By combining these three new idea, we can define a lot of new life games, which are called Life games of Ibadai type. We found some interesting life games of Ibadai type.

著者

奥居 哲 柴田 祥一 岡田 稔 川島 信

出版者

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

雑誌

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

巻号頁・発行日

vol.2003, no.92, pp.67-72, 2003-09-19

---

本発表は,卒業研究・ゼミナールのための研究室配属を一対多型安定結婚問題と見なし,安定結婚問題の解法アルゴリズムを用いた配属(以下,安定結婚配属)を試みた事例の分析に関する報告である.安定結婚配属を,第1 志望を特別に優先する発見的手法に基づく従来の配属に対して詳細に比較し,志望学生と受入れ先研究室の「満足度」の違いを調べた.「満足度」の評価には,複数の指標を組合せて用いた.その結果,学生,研究室共に,安定結婚配属の方が高い満足度が得られることが確認された.また,安定結婚配属において,定員の変化が配属結果に及ぼす影響についても調べた.その結果,定員の変化は,研究室間の配属数の格差に対して最も顕著な影響を与えることが観察された.We offer a case study of a laboratory assignment for under-graduate students as an instance of the stable marriage problems. Two assignment methods are considered; one adopts a 1-n stable marriage algorithm, while the other is based on heuristics giving absolute priority to the applicants for their most preferable laboratory. Using actual preference data, we compare two methods. Several kind of indices are introduced in order to evaluate satisfaction of students and faculty. Our analysis with respect to those indices indicates that the former method gives a more desirable coupling than the latter for both students and laboratories.

著者

藤重 悟 岩田 覚

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.103, pp.53-60, 2000-11-10

---

双劣モジュラ関数最小化を行なう最初の組合せ的な多項式時間アルゴリズムを提示する.このアルゴリズムは,劣モジュラ関数最小化に関するIwata-Fleischer-Fujishigeのスケーリング法の拡張に当たる.双劣モジュラ関数はデルタマトロイドの階数関数として現れる.本論文のアルゴリズムは,デルタマトロイド多面体の分離問題に関する最初の組合せ的な多項式時間解法を与える.マトロイド多面体の場合と異なり,デルタマトロイド多面体に関するこの問題に組合せ的な強多項式アルゴリズムを与えることは,依然として未解決である.This paper presents the first combinatorial, polynomial-time algorithm for minimizing bisubmodular functions, extending the scaling algorithm for submodular function minimization due to Iwata, Fleischer, and Fujishige. A bisubmodular function arises as a rank function of a delta-matroid. The scaling algorithm naturally leads to the first combinatorial polynomial-time algorithm for testing membership in delta-matroid polyhedra. Unlike the case of matroid polyhedra, it remains open to develop a combinatorial strongly polynomial algorithm for this problem.

著者

岡田 政則 岡本 栄司

出版者

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

雑誌

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

巻号頁・発行日

vol.1998, no.62, pp.57-64, 1998-07-22

---

実社会においては,プライバシー保護の観点からある種のランダムネスの利用の要求がある.この場合,完全にランダムな状態でなくても低コストで十分プライバシーが守られる状態が生成できれば都合が良い.本論文では,最初にシャフリングを定義し,シャフリング近似の概念を導入する.そのランダムネスの尺度としては相対エントロピーを利用し,ランダムネスのコストとしてシャフリングを生成する回路の素子の個数を利用する.このためにまずその個数にコストを表す関数としての妥当性があることを検証する.例として複数の投票所からなる投票集計のモデルを取り上げる.そこでは選挙とその投票結果のプライバシー保護をランダムネスとその生成コストの関係として考察している.Randomness is used for a protection of privacy in the actual world. To investigate randomness, we show the definition of the shuffling S_n of n input data; and, we define the pseudo-shuffling S^^^_n by S_2 0nly. The definition of randomness is represented by relative entropy, and the cost of randomness is expressed by the number of shuffling S_2 in pseudo-shuffling S_n. We consider pseudo-shuffling as an approximation of shuffling with some constraints. Finally, we show a problem related to ballot boxes in the election as an example.

著者

岡本 吉央

出版者

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

雑誌

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

巻号頁・発行日

vol.2002, no.70, pp.17-24, 2002-07-25

---

協力ゲーム理論において劣モジュラ性は非常に重要な性質であると認識されている.本論では,最小彩色ゲームと最小頂点被覆ゲームが劣モジュラ性を有する場合の特徴づけを示す.この特徴づけにより,与えられたグラフに対する最小彩色ゲーム/最小頂点被覆ゲームが劣モジュラであるかどうかを判定することが多項式時間で出来ることが分かる.それに関連して,ゲーム理論におけるシャプレイ値,および,付随するマトロイド構造についても述べる.Submodularity is considered as an important property in the field of cooperative game theory. In this report, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game is submodular or not for a given graph. Related to these results, the Shapley values and the associated matroid structures are also investigated.

著者

松浦 昭洋

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.119, pp.57-64, 2007-11-30

---

本稿では,ハノイの塔問題より一般化された再帰方程式T(n α β) = min_{1< t < n} {αT(n-t α β) + βS(t 3)}(S(t 3) = 2^t - 1 は3本の塔を持つハノイの塔問題に対する最小解)に対する厳密な解析を行い,その一般解を導出する。すなわち,αとβがα>2 なる任意の自然数であるとき,{T(n α β)} の階差数列がβ2^iα^j(i j > 0)なる自然数が昇順に並んだものであることを示す。In this paper, we make exact analysis of the recurrence relations generalized from the Tower of Hanoi problem of the form $T(n, \alpha, \beta) = \min_{\small{1\le t \le n}}\bigl\{ \alpha \, T(n-t, \alpha, \beta) + \beta \, S(t,3) \bigr\}$, where $S(t,3) = 2^t - 1$ is the optimal solution for the 3-peg Tower of Hanoi problem. It is shown that when $\alpha$ and $\beta$ are natural numbers and $\alpha \ge 2$, the sequence of differences of $T(n, \alpha, \beta)$'s, i.e., $T(n, \alpha, \beta) - T(n-1, \alpha, \beta) $, consists of numbers of the form $\beta 2^i \alpha^j \, (i, \, j \ge 0)$ lined in the increasing order.

著者

長井 歩

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.119, pp.73-80, 2007-11-30

---

多種多様なアルゴリズムのひしめくクラスタリング・アルゴリズムの中でも,近年注目されているものにNormalized Cutsがある.Norma』ized Cuts の最大の特徴は,固有値分解を行うなど行列計算を多用する点にある.基本的には,Normalized Cuts は分割クラスタ数を固定した上で,独自の評価基準のもとでクラスタ分割を得るという手法である.クラスタ数を固定するため,クラスタ数を変えることに対する柔軟性には乏しい.また Normalized Cuts は行列計算を行う際に粗行列化することによって計算量をO(n1.5) に減らしてるが,粗行列化できない場合にはO(n2.5) にまで増大してしまう.(nはデータ数である.)本論文で提案する階層型アルゴリズムは Normalized Cuts のこれらの問題点を解消できるいったん実行してしまえば,様々なクラスタ数の解を得ることが容易である.また,計算量は常にO(n2)である.アルゴリズムの基本的な骨格は古典的な階層型手法に似ている.しかし Normalized Cuts の評価基準を用いているために,両者の長所を併せ持つ.すなわち,Normalized Cuts のように任意の形状のクラスタを得られ,かつWard法のように樹形図を得ることができる.The characteristic mark of Normalized Cuts is that it relies on a linear algebraic approach including spectral decomposition. Basically, it obtains a partition by fixing the number K; of clusters. Therefore, it is not so easy to obtain partitions of various k, besides re-calculating. Moreover, when we cannot use sparse matrix, computational complexity jumps up to O(n2.5). We propose an hierarchical algorithm which can resolve these problems. It is easy to obtain partitions of various k after running the program. Its computational complexity is O(n2).

著者

白楽強 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.