Premium
A network flow algorithm to minimize beam‐on time for unconstrained multileaf collimator problems in cancer radiation therapy
Author(s) -
Ahuja Ravindra K.,
Hamacher Horst W.
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20047
Subject(s) - multileaf collimator , row , mathematics , linear programming , row and column spaces , matrix (chemical analysis) , integer programming , integer matrix , flow network , algorithm , mathematical optimization , integer (computer science) , maximum flow problem , computer science , beam (structure) , linear particle accelerator , nonnegative matrix , programming language , physics , materials science , eigenvalues and eigenvectors , symmetric matrix , database , quantum mechanics , optics , composite material
In this article, we study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated by decomposing a given m × n integer matrix into a positive linear combination of (0, 1) matrices with the strict consecutive 1's property in rows. We consider a special case in which no technical constraints have to be taken into account. In this situation, the rows of the intensity matrix are independent of each other and the problem is equivalent to decomposing m intensity rows—independent of each other—into positive linear combinations of (0, 1) rows with the consecutive 1's property. We demonstrate that this problem can be transformed into a minimum cost flow problem in a directed network that has the following special structures: (1) the network is acyclic; (2) it is a complete graph (that is, there is an arc ( i , j ) whenever i < j ); (3) each arc cost is 1; and (4) each arc is uncapacitated (that is, it has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in O( n ) time. Because we need to solve m such problems, the total running time of our algorithm is O( nm ), which is an optimal algorithm to decompose a given m × n integer matrix into a positive linear combination of (0, 1) matrices. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 36–41 2005