|
 
|
[JP12] Minimum decomposition into convex binary matrices
Revue Internationale avec comité de lecture : Journal Discrete Applied Math. , vol. 160, pp. 1164-1175, 2012, (doi:doi:10.1016/j.dam.2012.01.013)
motcle:
Résumé:
Motivated by Intensity Modulated Radiation Therapy, we consider the problem of the minimum decomposition of an integer matrix into hv-convex matrices with time and cardinality objectives. We study the special case where the matrix to decompose is a binary matrix (in this case, time decomposition and cardinality decomposition are the same). We prove that the decomposition into two hv-convex matrices or into two hv-convex polyominoes is polynomially solvable. For the decomposition into three hv-convex matrices the problem becomes NP-complete.
Equipe:
oc
BibTeX
| @article { | |||
| JP12, | |||
| title | = | "{Minimum decomposition into convex binary matrices}", | |
| author | = | "F. Jarray and C. Picouleau", | |
| journal | = | "Discrete Applied Math. ", | |
| year | = | 2012, | |
| volume | = | 160, | |
| pages | = | "1164-1175", | |
| doi | = | "doi:10.1016/j.dam.2012.01.013", | |
| } | |||
