Brief Papers: Parallel Algorithms for Finding a Near-Maximum Independent Set of a Circle Graph

Yoshiyasu Takefuji; Li Lin Chen; Kuo Chun Lee; John Huffman

doi:10.1109/72.80251

Brief Papers: Parallel Algorithms for Finding a Near-Maximum Independent Set of a Circle Graph

Yoshiyasu Takefuji, Li Lin Chen, Kuo Chun Lee, John Huffman

Research output: Contribution to journal › Article › peer-review

41 Citations (Scopus)

Abstract

A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph or the number of possible base pairs) not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. Our simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid (PSTV), than the formerly proposed structures. The simulator was tested in solving other problems.

Original language	English
Pages (from-to)	263-267
Number of pages	5
Journal	IEEE Transactions on Neural Networks
Volume	1
Issue number	3
DOIs	https://doi.org/10.1109/72.80251
Publication status	Published - 1990 Sept
Externally published	Yes

ASJC Scopus subject areas

Software
Computer Science Applications
Computer Networks and Communications
Artificial Intelligence

Access to Document

10.1109/72.80251

Cite this

@article{9e11efb8d3574a8e8c08f2bcddb50cbe,

title = "Brief Papers: Parallel Algorithms for Finding a Near-Maximum Independent Set of a Circle Graph",

abstract = "A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph or the number of possible base pairs) not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. Our simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid (PSTV), than the formerly proposed structures. The simulator was tested in solving other problems.",

author = "Yoshiyasu Takefuji and Chen, {Li Lin} and Lee, {Kuo Chun} and John Huffman",

year = "1990",

month = sep,

doi = "10.1109/72.80251",

language = "English",

volume = "1",

pages = "263--267",

journal = "IEEE Transactions on Neural Networks",

issn = "1045-9227",

publisher = "IEEE Computational Intelligence Society",

number = "3",

}

TY - JOUR

T1 - Brief Papers

T2 - Parallel Algorithms for Finding a Near-Maximum Independent Set of a Circle Graph

AU - Takefuji, Yoshiyasu

AU - Chen, Li Lin

AU - Lee, Kuo Chun

AU - Huffman, John

PY - 1990/9

Y1 - 1990/9

N2 - A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph or the number of possible base pairs) not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. Our simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid (PSTV), than the formerly proposed structures. The simulator was tested in solving other problems.

AB - A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph or the number of possible base pairs) not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. Our simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid (PSTV), than the formerly proposed structures. The simulator was tested in solving other problems.

UR - http://www.scopus.com/inward/record.url?scp=0025483481&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025483481&partnerID=8YFLogxK

U2 - 10.1109/72.80251

DO - 10.1109/72.80251

M3 - Article

AN - SCOPUS:0025483481

SN - 1045-9227

VL - 1

SP - 263

EP - 267

JO - IEEE Transactions on Neural Networks

JF - IEEE Transactions on Neural Networks

IS - 3

ER -

Brief Papers: Parallel Algorithms for Finding a Near-Maximum Independent Set of a Circle Graph

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this