Time complexity of gate assignment problem in one‐dimensional array
Takashi Fujii, Tohru Kikuno, Noriyoshi Yoshidas, Hideya Horikawa · Electronics and Communications in Japan (Part I Communications) · 1987
Abstract In the one‐dimensional array approach, a logic circuit is realized by arranging NAND (NOR) gates in a one‐dimensional array and interconnecting them. The horizontal length of the resultant layout of the logic circuit is determined uniquely by the number of given gates, while the vertical length varies depending on the order of assignment of gates. Thus, to minimize the area required, we must find a one‐dimensional assignment of gates so as to minimize the vertical length. This optimization problem (called problem G) has been formulated as a graph problem and has already been proved to be NP‐hard. In this paper, a restricted problem (called the problem R) is introduced anew wherein a connection of each net is restricted to be between two gates. The problem R plays an important role in developing a heuristic algorithm for the problem G. As for the time complexity, we show that the problem R is also NP‐hard.