PACKING SQUARES INTO A SQUARE

被引：106

作者：

LEUNG, JYT

TAM, TW

WONG, CS

YOUNG, GH

CHIN, FYL

机构：

[1] TULANE UNIV,DEPT COMP SCI,NEW ORLEANS,LA 70118

[2] UNIV HONG KONG,DEPT COMP SCI,HONG KONG,HONG KONG

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1990年 / 10卷 / 03期

关键词：

D O I：

10.1016/0743-7315(90)90019-L

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng. © 1990.

引用

页码：271 / 275

页数：5