| Presentation | 2016-01-18 A Study on Message Passing Algorithm for Counting Short Cycles in Sparse Bipartite Graphs Yuta Nakahara, Shota Saito, Toshiyasu Matsushima, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we propose an improvement of message passing algorithm for counting short cycles in sparse bipartite graphs. Let $g$ and $|E|$ denote the girth of the graph and number of edges respectively. In previous studies, algorithms are proposed for counting cycles of length $g, g+2,dots , 2g-2$ with complexity of $O(g|E|^2)$. Our proposed algorithm is able to count cycles of the same length of previous algorithm with lower complexity by limiting the nodes to process. Proposed algorithm have the complexity of $O(|E|d_u^{frac{g}{2}}d_w^{frac{g}{2}-1})$, where the node degrees of bipartite graph is constant $d_u, d_w$. Then computer simulation is provided to count the cycles of famous LDPC codes. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Bipartite graph / cycle / LDPC code / message passing |
| Paper # | IT2015-50,SIP2015-64,RCS2015-282 |
| Date of Issue | 2016-01-11 (IT, SIP, RCS) |
| Conference Information | |
| Committee | RCS / IT / SIP |
|---|---|
| Conference Date | 2016/1/18(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kwansei Gakuin Univ. Osaka Umeda Campus |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Signal Processing for Wireless Communications, Learning, Mathematical Science, Communication Theory, etc. |
| Chair | Makoto Taromaru(Fukuoka Univ.) / Yasutada Oohama(Univ. of Electro-Comm.) / Osamu Houshuyama(NEC) |
| Vice Chair | Hidekazu Murata(Kyoto Univ.) / Satoshi Denno(Okayama Univ.) / Yukitoshi Sanada(Keio Univ.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Makoto Nakashizuka(Chiba Inst. of Tech.) / Masahiro Okuda(Univ. of Kitakyushu) |
| Secretary | Hidekazu Murata(Mitsubishi Electric) / Satoshi Denno(NTT DoCoMo) / Yukitoshi Sanada(Univ. of Electro-Comm.) / Tadashi Wadayama(Wakayama Univ.) / Makoto Nakashizuka(NEC) / Masahiro Okuda(Ritsumeikan Univ.) |
| Assistant | Jun Mashino(NTT) / Tetsuya Yamamoto(Panasonic) / Takamichi Inoue(NEC) / Tomoya Tandai(Toshiba) / Toshihiko Nishimura(Hokkaido Univ.) / Takuya Kusaka(Okayama Univ.) / Takamichi Miyata(Chiba Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Radio Communication Systems / Technical Committee on Information Theory / Technical Committee on Signal Processing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on Message Passing Algorithm for Counting Short Cycles in Sparse Bipartite Graphs |
| Sub Title (in English) | |
| Keyword(1) | Bipartite graph |
| Keyword(2) | cycle |
| Keyword(3) | LDPC code |
| Keyword(4) | message passing |
| 1st Author's Name | Yuta Nakahara |
| 1st Author's Affiliation | Waseda University(Waseda Univ.) |
| 2nd Author's Name | Shota Saito |
| 2nd Author's Affiliation | Waseda University(Waseda Univ.) |
| 3rd Author's Name | Toshiyasu Matsushima |
| 3rd Author's Affiliation | Waseda University(Waseda Univ.) |
| Date | 2016-01-18 |
| Paper # | IT2015-50,SIP2015-64,RCS2015-282 |
| Volume (vol) | vol.115 |
| Number (no) | IT-394,SIP-395,RCS-396 |
| Page | pp.pp.13-18(IT), pp.13-18(SIP), pp.13-18(RCS), |
| #Pages | 6 |
| Date of Issue | 2016-01-11 (IT, SIP, RCS) |