論文

査読有り
2014年

An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths

DISCOVERY SCIENCE, DS 2014
  • Takeaki Uno
  • ,
  • Hiroko Satoh

8777
開始ページ
313
終了ページ
324
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
出版者・発行元
SPRINGER-VERLAG BERLIN

A chordless cycle (induced cycle) C of a graph is a cycle without any chord, meaning that there is no edge outside the cycle connecting two vertices of the cycle. A chordless path is defined similarly. In this paper, we consider the problems of enumerating chordless cycles/paths of a given graph G = (V, E), and propose algorithms taking O(vertical bar E vertical bar) time for each chordless cycle/path. In the existing studies, the problems had not been deeply studied in the theoretical computer science area, and no output polynomial time algorithm has been proposed. Our experiments showed that the computation time of our algorithms is constant per chordless cycle/path for non-dense random graphs and real-world graphs. They also show that the number of chordless cycles is much smaller than the number of cycles. We applied the algorithm to prediction of NMR (Nuclear Magnetic Resonance) spectra, and increased the accuracy of the prediction.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000360154800027&DestApp=WOS_CPL
URL
http://www.springer.com/us/book/9783319118116
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000360154800027

エクスポート
BibTeX RIS