文献

J-GLOBAL ID：201402254660079959   整理番号：14A1464300

「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野-5.超大規模なグラフ構造の効率的な処理技術

著者 (3件)： 戸田貴久 (電通大 大学院情報システム学研究科) ,  竹内聖悟 (JST-ERATO) ,  美添一樹 (JST-ERATO)
資料名： 電子情報通信学会誌  (Journal of the Institute of Electronics, Information and Communication Engineers)
巻： 97  号： 12  ページ： 1097-1102  発行年： 2014年12月01日 
JST資料番号： F0019A  ISSN： 0913-5693  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,大規模グラフ処理に関する三つの異なる課題を挙げ,実用上の性能を向上させる手法について解説する。はじめに,列挙問題における網羅的な場合分け処理を二分決定グラフを用いて効率化させる方法について述べる。次にSimpathアルゴリズムの並列化においてメモリ共有環境の性質を考慮し性能を向上させる例について述べる。そして,ゲーム木探索の大規模並列化におけるGPS将棋の例を述べ,分散ハッシュ表を用いた並列探索手法についても述べる。(著者抄録)

シソーラス用語： *二分決定グラフ ,  *数え上げ理論 ,  構造 ,  *並列化 ,  共有メモリ ,  分散メモリ ,  アルゴリズム ,  組合せ問題 ,  木探索 ,  木【グラフ】 ,  表
準シソーラス用語： Simpathアルゴリズム ,  *グラフ構造 ,  ゲーム木 ,  分散ハッシュテーブル

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

引用文献 (10件)：

• T. Eiter, K. Makino, and G. Gottlob, “Computational aspects of monotone dualization : A brief survey,“ Discrete Appl. Math., vol. 156, no. 11, pp. 2035-2049, June 2008.
• T. Eiter and G. Gottlob, “Hypergraph transversal computation and related problems in logic and AI,“ 8th European Conference on Logics in Artificial Intelligence, pp. 549-564, Italy, Sept. 2002.
• K. Murakami and T. Uno, “Efficient algorithms for dualizing large-scale hypergraphs,“ Discrete Appl. Math., vol. 170, pp. 83-94, June 2014.
• D.E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 1 : Bitwise Tricks & Techniques ; Binary Decision Diagrams, Addison-Wesley Professional, 12th edition, March 2009.
• T. Toda, “Hypergraph transversal computation with binary decision diagrams,“ 12th International Symposium on Experimental Algorithms, pp. 91-102, Rome, Italy, June 2013.

タイトルに関連する用語 (8件)： フカ ,  シギ ,  アルゴリズム ,  二分決定グラフ ,  離散構造 ,  応用 ,  大規模 ,  グラフ構造