Find in Library

Strong connected components (SCCs) mining is one of the classic problems in graph theory.It has practical requirements to design a serial SCCs mining algorithm with high efficiency.GRSCC algorithm can use SUB-RSCC function to discover SCCs of simple digraphs.SUB-RSCC function is formed by two operators of rough set theory (RST),<i>k</i>-step upper approximation set and <i>k</i>-step <i>R</i>-related,which are the main contributors to time consumption.Then the invocation times of SUB-RSCC decide the efficiency of GRSCC algorithm.Based on the SCCs correlations among vertices,GRSCC algorithm introduces granulation strategy to reduce the invocation times of SUB-RSCC function,then improve the mining efficiency.Two new SCCs correlations are found by analysis of SCCs in the framework of RST,then a new vertex granulation strategy is designed to granulate the vertex set of target digraphs.In order to reduce the invocation times of SUB-RSCC function to a greater extent,a method called <i>k</i>-step search of vertex granule is proposed.Finally,combining with GRSCC algorithm,an algorithm called KGRSCC for mining SCCs based on <i>k</i>-step search of vertex granule and RST is proposed.Experimental results show that,compared with RSCC,GRSCC and Tarjan algorithms,the proposed KGRSCC algorithm has better performance.