A dual of the rectangle-segmentation problem for binary matrices

Author(s)
Kalinowski, Thomas
Publication Date
2009-07-24
Abstract
We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons.
Citation
The Electronic Journal of Combinatorics, 16(1), p. 1-13
ISSN
1077-8926
Link
https://hdl.handle.net/1959.11/26801
Publisher
Electronic Journal of Combinatorics
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International
Title
A dual of the rectangle-segmentation problem for binary matrices
Type of document
Journal Article
Entity Type
Publication

Files:

NameSizeformatDescriptionLink