DocumentCode :
3230597
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
Volume :
3
fYear :
2007
fDate :
July 30 2007-Aug. 1 2007
Firstpage :
676
Lastpage :
681
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/SNPD.2007.87
Filename :
4287936
Link To Document :
بازگشت