文献

J-GLOBAL ID：201602202909085682   整理番号：16A0264375

メッセージ伝搬にもとづく疎な2部グラフ上のショートサイクル数え上げ法に関する研究

A Study on Message Passing Algorithm for Counting Short Cycles in Sparse Bipartite Graphs

著者 (3件)： 中原悠太 (早稲田大) ,  齋藤翔太 (早稲田大) ,  松嶋敏泰 (早稲田大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 394(IT2015 48-100)  ページ： 13-18  発行年： 2016年01月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,疎な2部グラフ上のショートサイクルをメッセージ伝搬によって数え上げるアルゴリズムの改良を提案する。従来研究では,2部グラフのガースをg,エッジ数を|E|とおいたとき,長さg,g+2,...,2g-2のサイクルを,O(g|E|²)の計算量で数え上げている。本研究では,従来のアルゴリズムのメッセージ更新処理を行うノードを制限することによって,従来研究と同じ長さのサイクルをより少ない計算量で数え上げることができることを示す。提案アルゴリズムの計算量は,ノード次数が一定の値d_u,d_wをとる2部グラフに対してはO(|E|d_u^g/2d_w^g/2-1)となる。サイクル数の知られている2部グラフとして,いくつかのLDPC符号に対し提案アルゴリズムを用いてショートサイクルを数え上げ,従来アルゴリズムと比較する。(著者抄録)

シソーラス用語： 部分グラフ ,  サイクル ,  *アルゴリズム ,  誤り訂正符号 ,  計算量 ,  数え上げ理論 ,  グラフ理論
準シソーラス用語： LDPC符号 ,  *メッセージパッシングアルゴリズム ,  二部グラフ

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (6件)： メッセージ ,  伝搬 ,  2部グラフ ,  ショート ,  サイクル ,  研究