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

fYear

2013

fDate

14-15 Dec. 2013

Firstpage

194

Lastpage

198

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Sciences and Applications (CSA), 2013 International Conference on

Conference_Location

Wuhan

Type

conf

DOI

10.1109/CSA.2013.52

Filename

6835578