連結グラフのランダム生成法について

• Item type: SIG Technical Reports(1)
• 公開日: 1998-01-22
• タイトル: 連結グラフのランダム生成法について
• タイトル / 言語: en
• タイトル: Random Generation of Connected Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院理工学研究科
• 著者所属: 早稲田大学理工学部情報学科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Waseda University Department of Computer and Information Science, Waseda University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Waseda University Department of Computer and Information Science, Waseda University
• 著者名: 矢農正紀; 二村, 良彦
• 著者名(英): Masanori, Yanoh; Yoshihiko, Futamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフアルゴリズムの精密な評価を行うためには、指定された頂点数nと辺数mを有し、かつランダムに生成された複数のラベル付き連結グラフが必要である。本稿では、頂点にラベルが付くか、辺に異なる重みが付く場合に、頂点n個かつ辺m本の連結グラフを一様ランダムに生成するアルゴリズムを提案する。このアルゴリズムは、構成比と呼ばれる部分グラフ数のグラフ数に対する割合を、計算機オーバーフローを回避して直接計算する方法に基づく。ランダム生成の前処理として、表の作成にO(^2n^)時間とO(n^)空間を要するが、これにより連結グラフを1個につきO()時間で生成することが可能である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a new method for generating random labeled connected graphs with n nodes and m edges for given n and m. The random graphs are to be used to conduct precise evaluation of graph algorithms. Our method is based on overflow free calculation of a composite ratio, i.e. the ratio of number of subgraphs against the number of all graphs. Using the ratio, we can uniformly generate a connected graph with n nodes and m edges in O(mn) time using preprocessing of O(m^2n^2) time O(mn^2) space.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 3(1997-AL-060), p. 1-8, 発行日 1998-01-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会