Linear Algorithm for a Cyclic Graph Transformation
- Authors: Lyubetsky V.A.1,2, Lyubetskaya E.1, Gorbunov K.1
-
Affiliations:
- Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
- Faculty of Mechanics and Mathematics
- Issue: Vol 39, No 9 (2018)
- Pages: 1217-1227
- Section: Part 1. Special issue “High Performance Data Intensive Computing” Editors: V. V. Voevodin, A. S. Simonov, and A. V. Lapin
- URL: https://journals.rcsi.science/1995-0802/article/view/203121
- DOI: https://doi.org/10.1134/S1995080218090147
- ID: 203121
Cite item
Abstract
We propose a linear time and linear space algorithm that constructs a minimal (in the total cost) sequence of operations required to transform a directed graph consisting of disjoint cycles into any graph of the same type. The following operations are allowed: double-cut-and-join of vertices and insertion or deletion of a connected fragment of edges; the latter two operations have the same cost. We present a complete proof that the algorithm finds the corresponding minimum. The problem is a nontrivial particular case of the general problem of transforming a graph into another, which in turn is an instance of a hard optimization problem in graphs. In this general problem, which is known to be NP-complete, each vertex of a graph is of degree 1 or 2, edges with the same name may repeat unlimitedly, and operations belong to a well-known list including the above-mentioned operations. We describe our results for the general problem, but the proof is given for the cyclic case only.
About the authors
V. A. Lyubetsky
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute); Faculty of Mechanics and Mathematics
Author for correspondence.
Email: lyubetsk@iitp.ru
Russian Federation, Bol’shoi Karetnyi per. 19, str. 1, Moscow, 127051; Moscow, 119991
E. Lyubetskaya
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
Email: lyubetsk@iitp.ru
Russian Federation, Bol’shoi Karetnyi per. 19, str. 1, Moscow, 127051
K. Gorbunov
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
Email: lyubetsk@iitp.ru
Russian Federation, Bol’shoi Karetnyi per. 19, str. 1, Moscow, 127051