TY - JOUR
AU - Antje Kiesel
AU - CĂ©line Engelbeen
PY - 2010/12/02
Y2 - 2019/08/20
TI - Binary matrix decompositions without tongue-and-groove underdosage for radiation therapy planning
JF - Algorithmic Operations Research
JA - AOR
VL - 5
IS - 2
SE - Articles
DO -
UR - https://journals.lib.unb.ca/index.php/AOR/article/view/12603
AB - 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.
ER -