Title :
A Quick Algorithm for Computing Core Based on the Positive Region
Author :
Cai, Wei-Dong ; Xu, Zhang-Yan ; Song, Wei ; Yang, Bing-ru
Author_Institution :
Univ. of Ji´´nan, Jinan
fDate :
July 30 2007-Aug. 1 2007
Abstract :
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(|CparU|2 ). For cutting down the time complexity of the algorithm, 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(|CparU|). On this condition, a new algorithm for computing core based on the positive region is designed with the simplified discernibility. Its time complexity is cut down to max{O(|CparU´posparU/C|), O(|CparU|)}.
Keywords :
computational complexity; matrix algebra; rough set theory; discernibility matrix; rough set theory; time complexity; Algorithm design and analysis; Artificial intelligence; Computer networks; Concurrent computing; Decision making; Distributed computing; Partial response channels; Partitioning algorithms; Set theory; Sorting; Complexity; Core; Positive region; Rough set; Simplified; discernibility matrix;
Conference_Titel :
Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference on
Conference_Location :
Qingdao
Print_ISBN :
978-0-7695-2909-7
DOI :
10.1109/SNPD.2007.87