Informatics and Applications
2017, Volume 11, Issue 1, pp 79-89
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 NP-hard 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):223-236.
- 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. Bra-ga. 2013. DCJ-indel and DCJ-substitution 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:38-51.
- Gorbunov, K. Yu., R. A. Gershgorin, and V.A. Lyubetsky 2015. Rearrangement and inference of chromosome structures. Mol. Biol. 49(3):327-338.
- Gorbunov, K.Yu., and V.A. Lyubetsky. 2016. Modi- fitsirovannyy algoritm preobrazovaniya khromosomnykh struktur: Usloviya absolyutnoy tochnosti [Modified algorithm for transformation of chromosome structures: Con-ditions of absolute accuracy]. Sovremennye informatsionnye tekhnologii i IT-obrazovanie [Modern Information Tech-nologies and IT Education] 12(1):162-172.
- Compeau, P E. C. 2013. DCJ-indel sorting revisited. Algorithm. Mol. Biol. 8:6.1-6.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 79-89
Cover Date
2017-02-30
DOI
10.14357/19922264170107
Print ISSN
1992-2264
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, 19-1 Bolshoy Karetny Per., Moscow 127051, Russian Federation
Faculty of Mechanics and Mathematics, M. V. Lomonosov Moscow State University, Main Building, Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
|