Novel graph-based algorithms for reconfigurable arrays

A generalized version of the repair-most method and an exhaustive search method for reconfigurable arrays in fabrication or compile time are presented. This generalized version of the method, instead of removing the most possible edges, as in the repair-most method, tries to 'free' as many vertices as possible in the bipartite graph at each iteration. Therefore, it can overcome the major defects of the repair-most one and runs in equal time complexity. This generalized method is called the free-most method. For evaluating the results generated from the free-most method, the authors also develop an exhaustive search method based on the vertex covering problem in graph theory and call it the vertex-cover method. >