The DT-Polynomial Approach to Discrete Time-Varying Network Flow Problems

This paper introduces a polynomial operator called the DT-polynomial as a novel approach to network flow problems. The class of networks dealt with is time-varying in the sense that the capacity, cost, and travel-time of each edge may vary in discrete time. The Dt-polynomial is a polynomial in two operators, D (delay) and T (time), which is used for describing the time-varying transmission characteristics. The paper starts with the mathematics involving the DT-polynomials. A new shortest arrival route algorithm is presented, and its computational complexity is found to be favorable in comparison with others such as Dijkstra's method and the potential method derived from Ford-Fulkerson's technique. Furthermore, a dynamic flow problem is formulated and analyzed in terms of DT-polynomials, and a latest-departure earliest-arrival schedule is given. Finally, a modified DT-polynomial is applied to digital filter networks.