Computing connected components of simple undirected graphs based on generalized rough sets

被引：10
作者：
Chen, Jinkun [1 ]
Li, Jinjin [1 ]
Lin, Yaojin [2 ]
机构：
[1] Zhangzhou Normal Univ, Dept Math & Informat Sci, Zhangzhou 363000, Peoples R China
[2] Zhangzhou Normal Univ, Dept Comp Sci & Engn, Zhangzhou 363000, Peoples R China
来源：
KNOWLEDGE-BASED SYSTEMS | 2013年 / 37卷
基金：
中国国家自然科学基金;
关键词：
Rough set; k-Step-upper approximation; Definable set; Connection; Connected component; EFFICIENT PARALLEL ALGORITHMS; KNOWLEDGE ACQUISITION; ATTRIBUTE REDUCTION; INFORMATION-SYSTEMS; APPROXIMATION;
D O I：
10.1016/j.knosys.2012.07.013
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
This paper studies the problem of computing connected components of a simple undirected graph based on generalized rough sets. Definable sets of generalized rough sets are used to characterize the connection of graphs. Based on the concept of k-step-upper approximations, an algorithm is designed for computing the connected components of a simple undirected graph. Experiments show that the new proposed algorithm gets a better performance compared to the classical algorithm. Also, this algorithm can be easily to realize in parallel and requires less processors. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：80 / 85
页数：6
相关论文
共 27 条
123