Title :
Game-theoretic approach to placement problems of rectilinear blocks solution of rectilinear jigsaw puzzle
Author :
Murai, Yasuyuki ; Tatsumi, Hisayuki ; Tokumasu, Shinji
Author_Institution :
Dept. of Inf. & Comput. Sci., Kanagawa Inst. of Technol., Japan
Abstract :
In this paper, a rectilinear jigsaw puzzle is taken up as a specialized placement problem such that it has at least one solution of placement, but not so many in general. In order to solve this problem, instead of adopting the well known iterative method, a new game-theoretic algorithm is developed by translating the problem to a checkmate problem of a game analogous to chess or shogi. It is proved by numerical experiments that this works well with good efficiency
Keywords :
VLSI; circuit layout CAD; game theory; integrated circuit layout; network topology; VLSI; checkmate problem; floorplan design; game-theoretic approach; placement problems; rectilinear blocks; rectilinear jigsaw puzzle; Circuit topology; Fixtures; Fluctuations; Iterative algorithms; Iterative methods; Numerical simulation; Shape; Simulated annealing; Very large scale integration;
Conference_Titel :
Nanotechnology, 2001. IEEE-NANO 2001. Proceedings of the 2001 1st IEEE Conference on
Conference_Location :
Maui, HI
Print_ISBN :
0-7803-7215-8
DOI :
10.1109/NANO.2001.966406
