Informatics and Applications
2017, Volume 11, Issue 1, pp 7989
ALGORITHM OF TRANSFORMATION OF A GRAPH INTO ANOTHER ONE WITH MINIMAL COST
 K. Yu. Gorbunov
 V.A. Lyubetsky
Abstract
The authors study orgraphs with any number of chains and cycles. Edges of orgraphs have unique names  natural numbers. There is a fixed list of operations that transform one graph into another. A cost is assigned to each operation. The task is to find the path of transformations with minimal total cost. This problem has a wide range of practical applications. The task is probably NPhard and, thus, can be solved only under constraints imposed on costs or graphs. Such solutions are proposed in the study. The corresponding algorithms are linear in time and memory and are proved to be exact (nonheuristic), i. e., to find the path of transformations with minimal cost. Many heuristic algorithms solving this problem are known and tested on various data, but the proposed solutions are the first exact solutions.
[+] References (8)
 Gorbunov, K. Yu., and V.A. Lyubetsky. 2016. Lineynyy al goritm kratchayshey perestroyki grafov pri raznykh tsenakh operatsiy [A linear algorithm of the shortest transformation of graphs under different operation costs]. Informatsionnye protsessy [Information Processes] 16(2):223236.
 Gorbunov, K.Yu., and V.A. Lyubetsky. 2017 (in press). Lineynyy algoritm minimal'noy perestroyki struktur [Linear algorithm of the minimal reconstruction of structures under different operation costs]. Problemyperedachi infor matsii [Problems of Information Transmission] 53(1).
 Lyubetsky, V. A., R. A. Gershgorin, A.V. Seliverstov, and K. Yu. Gorbunov. 2016. Algorithms for reconstruction of chromosomal structures. BMC Bioinformatics 17:40.1 40.23.
 Da Silva, P. H., R. Machado, S. Dantas, and M. D. V. Braga. 2013. DCJindel and DCJsubstitution distances with
distinct operation costs. Algorithm. Mol. Biol. 8:21.1 21.15.
 Compeau, P E. C. 2014. A generalized cost model for DCJ indelsorting. Algorithms in bioinformatics. Eds. D. G. Brown and B. Morgenstern. Lecture notes in computer science ser. Springer. 8701:3851.
 Gorbunov, K. Yu., R. A. Gershgorin, and V.A. Lyubetsky 2015. Rearrangement and inference of chromosome structures. Mol. Biol. 49(3):327338.
 Gorbunov, K.Yu., and V.A. Lyubetsky. 2016. Modi fitsirovannyy algoritm preobrazovaniya khromosomnykh struktur: Usloviya absolyutnoy tochnosti [Modified algorithm for transformation of chromosome structures: Conditions of absolute accuracy]. Sovremennye informatsionnye tekhnologii i ITobrazovanie [Modern Information Technologies and IT Education] 12(1):162172.
 Compeau, P E. C. 2013. DCJindel sorting revisited. Algorithm. Mol. Biol. 8:6.16.9.
[+] About this article
Title
ALGORITHM OF TRANSFORMATION OF A GRAPH INTO ANOTHER ONE WITH MINIMAL COST
Journal
Informatics and Applications
2017, Volume 11, Issue 1, pp 7989
Cover Date
20170230
DOI
10.14357/19922264170107
Print ISSN
19922264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
orgraph with chains and cycles; graph transformation; graph transformation with minimal total cost; exact linear algorithm; graph constraint; cost constraint; conditional shortest solution
Authors
K. Yu. Gorbunov and V.A. Lyubetsky ,
Author Affiliations
A.A. Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences, 191 Bolshoy Karetny Per., Moscow 127051, Russian Federation
Faculty of Mechanics and Mathematics, M. V. Lomonosov Moscow State University, Main Building, Leninskiye Gory, GSP1, Moscow 119991, Russian Federation
