An application of rough sets to graph theory

Abstract: 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. [Copyright &y& Elsevier]