Linear Algorithm for a Cyclic Graph Transformation
- Авторлар: Lyubetsky V.1,2, Lyubetskaya E.1, Gorbunov K.1
-
Мекемелер:
- Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
- Faculty of Mechanics and Mathematics
- Шығарылым: Том 39, № 9 (2018)
- Беттер: 1217-1227
- Бөлім: 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
Дәйексөз келтіру
Аннотация
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.
Негізгі сөздер
Авторлар туралы
V. Lyubetsky
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute); Faculty of Mechanics and Mathematics
Хат алмасуға жауапты Автор.
Email: lyubetsk@iitp.ru
Ресей, 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
Ресей, 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
Ресей, Bol’shoi Karetnyi per. 19, str. 1, Moscow, 127051