Balancing problems in acyclic networks (Q1327220)

The authors regard a balancing problem in acyclic networks. Arc lengths are called balanced if any two paths with common endpoints have the same length. The buffer assignment problem arises in a network if the sum of the added amounts is minimal, in such a way that the arc lengths are balanced. The authors give procedures which solve several generalizations of the problem in polynomial time. The network flow theory is used. The authors solve a weighted version of the problem for nonrooted networks and upper bounds of buffers. It is shown that the problem of balancing a network while minimizing the number of arcs with positive buffers is NP-hard.