An Algorithm for Counting Short Cycles in Bipartite Graphs

@article{citeulike:474701, abstract = {Let<tex>\$G=(cal Ucupcal W,cal E)\$</tex>be a bipartite graph with disjoint vertex sets<tex>\$,cal U\$</tex>and<tex>\$cal W\$</tex>, edge set<tex>\$cal E\$</tex>, and girth<tex>\$g\$</tex>. This correspondence presents an algorithm for counting the number of cycles of length<tex>\$g,break g+2,\$</tex>and<tex>\$g+4\$</tex>incident upon every vertex in<tex>\$cal Ucupcal W\$</tex>. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as<tex>\$cal O(gn^3)\$</tex>where<tex>\$n=max(vert cal Uvert,vert cal Wvert )\$</tex>.}, author = {Halford, T. R. and Chugg, K. M. }, citeulike-article-id = {474701}, journal = {Information Theory, IEEE Transactions on}, number = {1}, pages = {287--292}, posted-at = {2006-01-21 23:55:11}, priority = {2}, title = {An Algorithm for Counting Short Cycles in Bipartite Graphs}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=1564444}, volume = {52}, year = {2006} }

TY - JOUR ID - citeulike:474701 L3 - citeulike-article-id:474701 N2 - Let<tex>$G=(cal Ucupcal W,cal E)$</tex>be a bipartite graph with disjoint vertex sets<tex>$,cal U$</tex>and<tex>$cal W$</tex>, edge set<tex>$cal E$</tex>, and girth<tex>$g$</tex>. This correspondence presents an algorithm for counting the number of cycles of length<tex>$g,break g+2,$</tex>and<tex>$g+4$</tex>incident upon every vertex in<tex>$cal Ucupcal W$</tex>. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as<tex>$cal O(gn^3)$</tex>where<tex>$n=max(vert cal Uvert,vert cal Wvert )$</tex>. IS - 1 JF - Information Theory, IEEE Transactions on EP - 292 TI - An Algorithm for Counting Short Cycles in Bipartite Graphs VL - 52 SP - 287 AU - Halford, TR AU - Chugg, KM PY - 2006/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1564444 ER -