|
Problemy Peredachi Informatsii, 2017, Volume 53, Issue 1, Pages 60–78
(Mi ppi2228)
|
|
|
|
This article is cited in 7 scientific papers (total in 7 papers)
Large Systems
Linear algorithm for minimal rearrangement of structures
K. Yu. Gorbunov, V. A. Lyubetsky Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia
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.
Received: 29.12.2014 Revised: 25.04.2016
Citation:
K. Yu. Gorbunov, V. A. Lyubetsky, “Linear algorithm for minimal rearrangement of structures”, Probl. Peredachi Inf., 53:1 (2017), 60–78; Problems Inform. Transmission, 53:1 (2017), 55–72
Linking options:
https://www.mathnet.ru/eng/ppi2228 https://www.mathnet.ru/eng/ppi/v53/i1/p60
|
Statistics & downloads: |
Abstract page: | 253 | Full-text PDF : | 40 | References: | 37 | First page: | 12 |
|