Title :
An Algorithm for Approximating Set Cover and Its Application on Logic Circuit Optimization
Author :
Wanggen Li ; Changzi Wang ; Liang Wang ; Zhenxing Hu
Author_Institution :
Sch. of Math. & Comput. Sci., Anhui Normal Univ., Wuhu, China
Abstract :
The set covering question is NP-Hard problem on optimized combination. In this paper, we presented Simplifying and Selecting-Excellence Algorithm (SSE) based on the strategy. The main ideas of it: Before a most possible set was chosen, the set covering problem was simplified and the necessary sets were chosen. The obtained solution is more approximate to the exact solution than greedy algorithm. The time complexity is index level, but it is superior to O (m3 and mn2) when the connection degree is less than a certain range. In the multi-input logic circuit simplification, SSE algorithm is much better than QM algorithm.
Keywords :
circuit optimisation; computational complexity; logic circuits; NP-hard problem; QM algorithm; SSE algorithm; approximating set cover; exact solution; greedy algorithm; index level; logic circuit optimization; multiinput logic circuit simplification; set covering problem; simplifying and selecting-excellence algorithm; time complexity; Algorithm design and analysis; Approximation algorithms; Approximation methods; Computers; Educational institutions; Greedy algorithms; Logic circuits; SSE Algorithm; logic circuit simplification; most possible set; multi input; set cover;
Conference_Titel :
Computer Sciences and Applications (CSA), 2013 International Conference on
Conference_Location :
Wuhan
DOI :
10.1109/CSA.2013.52
