Efficient solution of linear diophantine equations (Q1121310)

The paper gives a new method for finding complete information about all nonnegative solutions of a linear homogeneous or inhomogeneous diophantine equation \[ \sum_{i=1}^{m}a_ix_i- \sum_{j=1}^{n}b_jy_j=c, \] where the \(a_i's\) and \(b_j's\) are positive integers and \(c\) is \(0\) resp. a positive integer. The equation is represented by a labelled digraph and the given graph algorithm generates finitely many minimal solutions; all other solutions are nonnegative integer linear combinations of these minimal solutions. The algorithm is compared with some other known algorithms and seems to be much more effective. An appendix gives a PASCAL implementation of the algorithm.