A robust method for searching the smallest set of smallest rings with a path-included distance matrix.

Full Abstract

The perception of rings in graphs is widely used in many fields of science and engineering. Algorithms developed in the chemistry community, called smallest set of smallest rings (SSSR), applicable only for simple graphs or chemical structures. In contrast, algorithms developed by the computer science community, called minimum cycle basis (MCB) are identical to SSSR yet exhibit greater robustness. MCB-based algorithms can correctly reveal all rings in any complex graph. However, they are slow when applied to large complex graphs due to the inherent limitations of the algorithms used. Here, we suggest a heuristic method called RP-Path. This method is a robust, simple, and fast search method with O(n(3)) runtime algorithm that correctly identifies the SSSR of all of the test case of complex graphs by using approach different from the MCB-based method. Both the robustness and improvement in speed are achieved by using a path-included distance matrix and describing the characteristic features of rings in the matrix. This method is accurate and faster than any other methods and may find many application in various fields of science and engineering that use complicated graphs with thousands of nodes.

Author information

Author/s: Lee, Chang Joon (CJ); Kang, Young-Mook (YM); Cho, Kwang-Hwi (KH); No, Kyoung Tai (KT);

Affiliation: Department of Biotechnology, Yonsei University, Seoul 120-749, Korea.

Journal and publication information

Publication Type: Journal Article; Research Support, Non-U.S. Gov't

Journal: Proceedings of the National Academy of Sciences of the United States of America (Proc Natl Acad Sci U S A), published in United States. (Language: eng)

Reference: 2009-Oct; vol 106 (issue 41) : pp 17355-8

Dates: Created 2009/10/15; Completed 2009/11/03; Revised 2009/11/06;

PMID: 19805142, status: MEDLINE (last retrieval date: 11/9/2009, IMS Date: )

Sourced from the National Library of Medicine. Abstract text and other information may be subject to copyright.

External Links for this article
(including full text providers, if available):

Click Electronic Full-text Provider Links to see options for finding the electronic full text links to this article. Note there may be a subscription or fee required for access to the full text. See our FAQ for information on finding FREE full text articles.

This article may also be located in paper journal collections available in many libraries. Use the Journal and Publication Information above to find the full article.