Dynamic min-max problems (Q1300102)

The authors describe a method to check the solvability of a set of linear equations in the (max,min,+) algebra and some extensions to dynamic and periodic systems. The paper contains new results on a special class of weighted graphs, i.e., min-max graphs: 1. A relation between potential functions of dynamic and weight transformed static graphs is derived. 2. An effective pseudo-polynomial algorithm for the determination of the period of min-max systems is presented. 3. Results on the existence and uniqueness of the period of a dynamic min-max system are given. 4. Results on the uniqueness of the periods in the quasi-periodic case are given as well as algorithms to determine these periods. The main theorem is: The period function of a given static graph is unique.