Finding strongly connected components of simple digraphs based on generalized rough sets theory
Finding strongly connected components of simple digraphs based on generalized rough sets theory
复制标题
基于广义粗糙集理论寻找简单有向图的强连通分量
DOI：
10.1016/j.knosys.2018.02.038
复制
发表时间：
2018-06
影响因子：
8.8
通讯作者：
Guoyin Wang
中科院分区：
文献类型：
--
作者：
Taihua Xu;Guoyin Wang
粗糙集理论不善于从有向图这种关系数据中发现知识。为了解决这一问题，本文引入了由简单有向图导出的二元关系，并在广义粗糙集理论的框架下提出了k步R-相关集的概念。另外，在二元关系和有向图的相互表示的基础上，我们首先研究了广义粗糙集理论和图论之间的关系。在这项工作中建立的关系，使人们有可能使用广义粗糙集理论找到强连接的简单有向图，以前只能通过图形算法的组件。在上述工作的基础上，特别是k步R相关集的基础上，提出了相应的算法。通过一系列实验对算法进行了验证。结果表明，我们的算法提供了可比的性能，经典的Tarjan算法。此外，该算法可以并行实现。其并行性能可与现有的最先进的并行算法相媲美。
Rough sets theory is not good at discovering knowledge from digraphs which is a kind of relational data. In order to solve this problem, we introduce binary relations derived from simple digraphs and propose a new concept ofk-stepR-related set in the framework of generalized rough sets theory. In addition, we first investigate the relationships between generalized rough sets theory and graph theory on the basis of mutual representation between binary relations and digraphs. The relationships established in this work make it possible to use generalized rough sets theory to find strongly connected components of simple directed graphs, which previously can be solved only by graph algorithms. An algorithm is correspondingly developed based on the above works, especiallyk-stepR-related set. A series of experiments are carried out to test the proposed algorithm. The results show that our algorithm provides comparable performance to the classical Tarjan algorithm. In addition, the proposed algorithm can be implemented in parallel. And its parallel performance is comparable to existing state-of-the-art parallel algorithms.
登录
查看更多内容
基于模糊TOPSIS和粗糙集的产品初期失效机理分析方法
DOI：
10.1016/j.engappai.2015.06.002
发表时间：
2016-01-01
影响因子：
8
作者：
He, Yi-Hai;Wang, Lin-Bo;Xie, Min
通讯作者：
Xie, Min
DOI：
10.1007/978-3-319-99368-3
发表时间：
2018-10
期刊：
--
影响因子：
--
作者：
R. Efendi;Voni Apriana Dewi;Rahmadeni;Sri Basriati;Dadang Syarif
通讯作者：
R. Efendi;Voni Apriana Dewi;Rahmadeni;Sri Basriati;Dadang Syarif
DOI：
10.1007/978-3-662-46681-0_56
发表时间：
2015-04
期刊：
--
影响因子：
--
作者：
E. Renault;A. Duret-Lutz;F. Kordon;D. Poitrenaud
通讯作者：
E. Renault;A. Duret-Lutz;F. Kordon;D. Poitrenaud
DOI：
10.1142/s0218488513500074
发表时间：
2013-02-01
影响因子：
1.5
作者：
Gao, Xiulian;Gao, Yuan
通讯作者：
Gao, Yuan
DOI：
10.1016/j.ins.2007.12.012
发表时间：
2008-05
期刊：
Inf. Sci.
影响因子：
--
作者：
Junhua Zhang;Yuanyuan Wang
通讯作者：
Junhua Zhang;Yuanyuan Wang