Ei. Goldberg et al., THEORY AND ALGORITHMS FOR FACE HYPERCUBE EMBEDDING, IEEE transactions on computer-aided design of integrated circuits and systems, 17(6), 1998, pp. 472-488
We present a new matrix formulation of the face hypercube embedding pr
oblem that motivates the design of an efficient search strategy to fin
d an encoding that satisfies all faces of minimum length. Increasing d
imensions of the Boolean space are explored; for a given dimension con
straints are satisfied one at a time. The following features help to r
educe the nodes of the solution space that must be explored: candidate
cubes instead of candidate codes are generated, cubes yielding symmet
ric solutions are not generated, a smaller sufficient set of solutions
(producing basic sections) is explored, necessary conditions help dis
card unsuitable candidate cubes, early detection that a partial soluti
on cannot be extended to be a global solution prunes infeasible portio
ns of the search tree. We have implemented a prototype package minimum
input satisfaction kernel (MINSK) based on the previous ideas and run
experiments to evaluate it. The experiments show that MINSK is faster
and solves more problems than any available algorithm. Moreover, MINS
K is a robust algorithm, while most of the proposed alternatives are n
ot. Besides most problems of the complete Microelectronics Center of N
orth Carolina (MCNC) benchmark suite, other solved examples include an
important set of decoder programmable logic arrays (PLA's) coming fro
m the design of microprocessor instruction sets.