Linear algorithm for minimal rearrangement of structures

Abstract

We propose a linear time and linear space algorithm which constructs a minimal sequence of operations rearranging one structure (directed graph of cycles and paths) into another. Structures in such a sequence may have a varying number of edges; a list of operations is fixed and includes deletion and insertion of a fragment of a structure. We give a complete proof that the algorithm is correct, i.e., finds the corresponding minimum.