MPQ-trees for the orthogonal packing problem
Abstract
Given a set of rectangular items of different sizes and a rectangular container, the aim of the bi-dimensional Orthogonal Packing Problem (OPP-2 for short) is to decide whether there exists a non-overlapping packing of the items in this container. The rotation of items is not allowed. In this paper we present a new exact algorithm for solving OPP-2, based upon the characterization of solutions using interval graphs proposed by Fekete and Schepers. The algorithm uses MPQ-trees, which were introduced by Korte and Möhring to recognize interval graphs.
Origin : Files produced by the author(s)
Loading...