Vol 5 No 2 (2010)

Binary matrix decompositions without tongue-and-groove underdosage for radiation therapy planning

Antje Kiesel
University of Rostock
Céline Engelbeen
Université Libre de Bruxelles
Published December 2, 2010
  • intensity modulated radiation therapy (IMRT),
  • consecutive ones property,
  • tongue-and-groove constraint
How to Cite
Kiesel, A., & Engelbeen, C. (2010). Binary matrix decompositions without tongue-and-groove underdosage for radiation therapy planning. Algorithmic Operations Research, 5(2), Pages 119 - 132. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12603


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.