抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本研究では,疎な2部グラフ上のショートサイクルをメッセージ伝搬によって数え上げるアルゴリズムの改良を提案する。従来研究では,2部グラフのガースをg,エッジ数を|E|とおいたとき,長さg,g+2,...,2g-2のサイクルを,O(g|E|
2)の計算量で数え上げている。本研究では,従来のアルゴリズムのメッセージ更新処理を行うノードを制限することによって,従来研究と同じ長さのサイクルをより少ない計算量で数え上げることができることを示す。提案アルゴリズムの計算量は,ノード次数が一定の値d
u,d
wをとる2部グラフに対してはO(|E|d
ug/2d
wg/2-1)となる。サイクル数の知られている2部グラフとして,いくつかのLDPC符号に対し提案アルゴリズムを用いてショートサイクルを数え上げ,従来アルゴリズムと比較する。(著者抄録)