Probabilistic analysis and algorithms for reconfiguration of memory arrays
Wei Shi, W.K. Fuchs · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1992
Reconfiguration of memory arrays with spare rows and columns has been shown to be an NP-complete problem. An analysis of average-case time complexities of several existing heuristics is presented, as well as a provably average-case polynomial-time algorithm for reconfiguration of memories with spare rows and columns. The algorithm runs faster than previous heuristics when the problem size is larger.>