We propose an alignment-based average delay time estimation algorithm between two time series in the propagation of time-varying delay. Though the number of the minimum cost alignments may be exponential in the length of the time series, the proposed algorithm takes account of all such alignments, and as a post-alignment process, it runs in time linear in the number of the nodes in the minimum cost alignment graph, which is at most the length squared. The efficiency of our algorithm is confirmed through numerical experiments compared to the naive enumeration algorithm using recursive calls to traverse the graph.
