A linear algorithm for the shortest transformation of graphs with different operation costs

Abstract

A novel time- and memory-efficient algorithm for solving the problem of finding the most economical (i.e., having the lowest overall cost) transformation of an arbitrary oriented graph representing a disjoint union of chains and cycles into another graph of the same type is proposed. The correctness of this algorithm (i.e., the fact that it always yields the minimum of the overall cost functional) and the linearity of the estimated memory and time of its operation are demonstrated.