An application of rough sets to graph theory

作者：Chen Jinkun; Li Jinjin

来源：Information Sciences, 2012, 201: 114-127.

DOI：10.1016/j.ins.2012.03.009

• Rough set
• SP-relation
• Quasi-outer definable set
• Graph theory
• Independent set
• Bipartite graph

This paper studies the testing bipartiteness of simple undirected graphs based on generalized rough sets. A new binary relation induced from a simple undirected graph is first defined. The concept of quasi-outer definable sets is then introduced, and some of its important properties are investigated. Finally, based on the quasi-outer definable set, a new algorithm is designed for testing bipartiteness of a simple undirected graph. Experiments show that the proposed algorithm is more efficient than the traditional one when the graph is represented by an adjacency matrix.

• 出版日期2012-10-15
• 单位闽南师范大学