@article{Kiesel_Engelbeen_2010, title={Binary matrix decompositions without tongue-and-groove underdosage for radiation therapy planning}, volume={5}, url={https://journals.lib.unb.ca/index.php/AOR/article/view/12603}, abstractNote={In the present paper we consider a particular case of the segmentation problem arising in the elaboration of radiation therapy plans. This problem consists in decomposing an integer matrix A into a nonnegative integer linear combination of some particular binary matrices called segments which represent fields that are deliverable with a multileaf collimator. For the radiation therapy context, it is desirable to find a decomposition that minimizes the beam-on time, that is the sum of the coefficients of the decomposition. Here we investigate a variant of this minimization problem with an additional constraint on the segments, called the tongue-and-groove constraint. Although this minimization problem under the condition that the used segments have to respect the tongue-and-groove constraint has already been studied, the complexity of it is still unknown. Here we prove that in the particular case where A is a binary matrix this problem is polynomially solvable. We provide a polynomial procedure that finds such a decomposition with minimal beam-on time. Furthermore, we show that the beam-on time of an optimal decomposition (but not the segmentation itself) can be found by determining the chromatic number of a related perfect graph.}, number={2}, journal={Algorithmic Operations Research}, author={Kiesel, Antje and Engelbeen, CĂ©line}, year={2010}, month={Dec.}, pages={Pages 119 - 132} }