ラベル付き連結グラフ高速ランダム生成のための構成比近似法
スポンサーリンク
概要
- 論文の詳細を見る
頂点にラベルの付いた連結グラフのランダム生成は,グラフアルゴリズムの評価のために重要である.本稿では,グラフのランダム生成に必要な構成比を近似する方法を提案し,それによって高速な生成が可能であることを示す.グラフアルゴリズムの評価には,特定の性質を有してランダムに生成されたグラフが多量に必要である.また,ネットワークのシミュレーション等に関しても,テストデータとしてランダムに生成されたグラフを必要とすることがある.その際,グラフ生成が高速であることと同時に,生成されるグラフのランダムネスに関しても高精度であることが要求される.例えば,[1]において最小全域木問題を線形時間で解く確率的アルゴリズムが示されているが,このアルゴリズムの検証を実際に行うためには,テストデータとしてランダムに生成された重み付き連結無向グラフが必要となる.このようなグラフは,ランダムに生成されたラベル付き連結無向グラフから生成可能である[6].指定された頂点数nと辺数mを持ち,頂点にラベルの付いた連結無向グラフをランダムに生成する既存の方法として,以下のものが挙げられる.頂点数nの木をランダムに生成し,これにm-m+1本の辺をランダムに付け加えることによって連結グラフを生成できる(全域木法).また,m本の辺をランダムに決定して生成されたグラフが連結となるまで繰り返して,連結グラフを生成する方法もある(生成検査法).或いは,構成比というグラフ総数に関する指標を用いて,ランダムにグラフを生成することができる(構成比法).しかし,全域木法に関してはランダムネスの精度に,生成検査法と構成比法に関しては生成時間に問題があり,必ずしも実用可能ではない.また,これら以外で効率的なグラフ生成を可能とする方法は,我々の調査では見出せなかった.本稿では,構成比を高い精度で近似する単純な近似式を提案する.それにより,構成比法によるグラフ生成の時間を改善し,大規模なグラフに関しても現実的な時間で生成できることを示す.
- 2003-07-25
著者
関連論文
- 「計算過程の部分評価」再び
- 累積変数を用いるリスト処理関数とその融合法
- Recursion Removal under Environments with Cache and Garbage Collection (Program Transformation, Symbolic Computation and Algebraic Manipulation)
- 木再帰プログラムからの再帰還元(一般発表)
- 再帰除去のごみ回避効果
- ある種の木再帰プログラムからの再帰除去
- ラベル付き連結グラフ高速ランダム生成のための構成比近似法
- 単純指標を持つ乱順列の高速生成法
- ソフトウェア性能評価のためのランダムデータ高速生成法 (第54回全国大会 (平成9年前期 於 : 千葉工大) 大会優秀賞受賞論文 (11件)
- ソフトウェア性能評価のためのランダムデータ高速生成法
- 単純指標を持つ乱順列の高速生成法
- 再帰除去の効果
- 整列法評価のためのランダム順列生成法
- 線形再帰プログラムからの再帰除去法
- 整列法評価のためのランダム順列の生成
- プログラム変換における数式処理の役割
- 20世紀の名著名論 : John McCarthy : Recursive Functions of Symbolic Expressions and Their Computations by Machine
- 単一後継関数を持つ再帰プログラムからの再帰除去
- LB-1 単一後継関数を持つ再帰プログラムからの再帰除去及び閉式化(B. ソフトウェア)
- LA-13 連結グラフの高速ランダム生成法(A. アルゴリズム・基礎)
- 再帰プログラム部分計算のための停止性判定法
- 葉数最適整列法LOASの実用化方式
- 数式処理系を利用したプログラム変換 (プログラム変換と記号・数式処理)
- 一般部分計算(GPC)における定理証明系と停止条件の判定 (プログラム変換と記号・数式処理)
- 一般部分計算法(GPC)によるプログラム自動生成 (プログラム変換と記号・数式処理)
- 3K-5 一般部分計算(GPC)の実験システムの実装
- O(m+n)時間及びスペースのランダムグラフ生成法
- 線形再帰プログラムからの再帰除去法の実現とその問題点(一般発表)
- 連結グラフのランダム生成のための構成比直接計算法
- オブジェクトを用いた計算モデルとその2次元トレーサへの応用
- 線形再帰プログラムからの再帰除去法の実現
- 母関数を用いたプログラム変換
- P区間表 : 区間に関するプログラム作成問題のためのデータ構造
- P区間表とそのプログラミング教育における効果
- 葉数最適整列法LOASとその実現法
- 葉数適応整列法LOASの最適性
- ランダムデータジェネレータジェネレータ(RDGG)の開発
- 適応整列法の評価
- ランダムデータサーバの開発
- 線形再帰プログラムからの再帰除去とその実際的効果
- 連結グラフのランダム生成法について
- アルゴリズム工学ワークショップ(WAE '97)報告
- 葉数最適整列法LOASの実現法