On the equivalence of pull-up transistor assignment in PLA folding and distribution graph
Wing Ning Li · 1994
Pull-up transistor assignment is one of the tasks in product term foMing of a Programmable Logic Array (PILA).This problem can be solved, in polynomial time, fLY first modeling it as a distribution graph, and then as a flow network.The pull-up transistor assignment problem seems simpler than the distribution graph problem.Thus, it may be possible to model the problem, differently (without using a distribution graph) and obtain asymptotically more efficient algorithms.In this paper, we show that the modeling is not the issue.In fact, the distribution graph problem can also be modeled as the pull-up transistor assignment problem.Hence, finding a more efficient algorithm for the pull-up transistor assignment problem is equivalent to having a more efficient algorithm for the distribution graph problem.