Quick algorithm for computing core based on the positive region
Zhangyan Xu, Yang Bing-ru · Systems engineering and electronics · 2006
Some scholars provided the discernibility matrix based on the positive region.The time complexity of the algorithm for computing core with this discernibility matrix is O(|C‖U|~2).For cuting down the time complexity of the algorithm for computing core,the definition of simplified discernibility matrix based on the positive region and the corresponding definition of the core are provided.At the same time,it is proved that this core is equivalent to the core based on the positive region.Since the partition of U/C is the key process for computing simplified discernibility matrix,a quick algorithm for computing U/C is designed with the idea of radix sorting.Its time complexity is O(|C‖U|).On this condition,a new algorithm for computing core based on the positive region is designed with the simplified discernibility matrix.Its time complexity is cut down to max{O(|C‖U|),O(|C‖U/C‖U~′_(pos)|)}.