文献

J-GLOBAL ID：201902230641926886   整理番号：19A0010736

非同型な2端子直並列グラフの列挙とランダムサンプリング

Enumeration and Random Sampling of Nonisomorphic Two-Terminal Series-Parallel Graphs

著者 (7件)： 伝住周平 (東大) ,  堀山貴史 (埼玉大) ,  栗田和宏 (北大) ,  中畑裕 (奈良先端科学技術大学院大) ,  鈴木浩史 (北大) ,  和佐州洋 (国立情報学研) ,  山崎一明 (北陸先端科学技術大学院大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 216(COMP2018 9-20)(Web)  ページ： 55-62 (WEB ONLY)  発行年： 2018年09月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 2端子直並列グラフとは,2つの頂点とそれらをつなぐ1つの辺からなるグラフに対して,次の2種類の操作を繰り返し適用することで得られる多重グラフのことをいう:(S操作)2つのグラフを直列に接続する,(P操作)2つのグラフを並列に接続する。本稿では,自然数nが与えられた時,辺数がnとなる2端子直並列グラフの全てからなる集合を求める漸化式を与える。さらに,与えた漸化式に基づいて,全ての解を実際に出力するアルゴリズムおよびランダムサンプリングアルゴリズムの構築についても議論する。いずれのアルゴリズムも,出力する解1つあたり多項式時間および多項式領域を必要とするアルゴリズムである。(著者抄録)

シソーラス用語： *グラフ ,  *無作為抽出 ,  計算量 ,  アルゴリズム ,  数え上げ理論 ,  時間計算量
準シソーラス用語： *ランダムサンプリング

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (24件)：

• S. Ruggieri, “Enumerating distinct decision trees,” Proceedings of the 34th International Conference on Machine Learning, eds. by D. Precup and Y.W. Teh, vol.70, pp.2960-2968, Proceedings of Machine Learning Research, PMLR, International Convention Centre, Sydney, Australia, 06-11 Aug 2017.
• N.K. Ahmed, J. Neville, R.A. Rossi, and N. Duffield, “Efficient graphlet counting for large networks,” 2015 IEEE International Conference on Data Mining, pp.1-10, Nov. 2015.
• S. Hara and T. Maehara, “Enumerate lasso solutions for feature selection,” 2017.
• L. Segoufin, “Enumerating with constant delay the answers to a query,” ICDT 2013: the 16th International Conference on Database Theory, pp.10-20, ACM Press, Genoa, Italy, mar 2013.
• R. Milo, “Network Motifs: Simple Building Blocks of Complex Networks,” Science, vol.298, no.5594, pp.824-827, oct 2002.

タイトルに関連する用語 (2件)： グラフ ,  ランダムサンプリング