A Surjective Mapping from Permutations to Room-to-Room Floorplans

Ryo FUJIMAKI  Toshihiko TAKAHASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.4   pp.823-828
Publication Date: 2007/04/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.4.823
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
floorplan,  representation,  permutation,  room-to-room,  

Full Text: PDF>>
Buy this Article




Summary: 
A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. Heuristic search algorithms are used to find desired floorplans in applications, including sheet-cutting, scheduling, and VLSI layout design. Representation of floorplan is critical in floorplan algorithms, because it determines the solution space searched by floorplan algorithms. In this paper, we show a surjective mapping from permutations to room-to-room floorplans. This mapping gives us a simple representation of room-to-room floorplans.