ネットワークの回線交換固定ルーティングの評価

スポンサーリンク

概要

論文の詳細を見る
小文では, 経路固定回線交換ネットワーク上の置換ルーティング問題について考察する. N点から成る2次元正方格子上の任意の置換に対する最適なスケジューリングの大きさは, O (√<N>) であることが知られている. 小文では, 最大次数ΔのN点から成る任意のネットワークにおいて, 任意の置換に対する最適なスケジューリングの大きさは, Ω (√<N>/Δ) であることを示す. また, N点ハイパーキューブにおいて, 任意の置換に対する, 最適なO (√<N>/log N) の大きさを持つスケジューリングを示し, そのようなスケジューリングは, N点ハイパーキューブ上で対数多項式並列時間で見つけることができることも示す. さらに, dが偶数であるとき, N点から成るd次元正方格子上の任意の置換に対する最適なスケジューリングの大きさは, Θ (√<N>) であることも示す.
社団法人電子情報通信学会の論文
1998-01-30

著者

関連論文

もっと見る

スポンサーリンク