Graph theoretic analysis of PLA folding heuristics

摘要

Because the problem of folding a programmable logic array (PLA) to its smallest possible area is NP-complete, the design and analysis of PLA-folding heuristics is important. In this paper, we study PLA-folding heuristics from a theoretical perspective, using the folding ratio of the heuristic to characterize its worst case behavior. In the first portion of this paper, we obtain best possible bounds on the folding ratios of several practical and intuitively appealing heuristics. These results show that for arbitrary PLAs, each of the heuristics exhibits unbounded worst-case behavior. Moreover, the results of Ravi and Lloyd (SIAM J. Comput. 17 (1988), 696–710) strongly suggest that no polynomial time approximation algorithm can have a constant folding ratio for arbitrary PLAs. Thus in the second portion of this paper, we analyze the performance of heuristics for certain restricted classes of PLAs characterized by special classes of intersection graphs.