Algorithm of transformation of a graph into another one with minimal cost
K. Yu. Gorbunova, V. A. Lyubetskyba
a A. A. Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences, 19-1 Bolshoy Karetny Per., Moscow 127051, Russian Federation
b Faculty of Mechanics and Mathematics, M. V. Lomonosov Moscow State University, Main Building, Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
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.
orgraph with chains and cycles; graph transformation; graph transformation with minimal total cost; exact linear algorithm; graph constraint; cost constraint; conditional shortest solution.
|Russian Science Foundation
|The study was supported by the Russian Science Foundation (project No. 14-50-00150).
PDF file (259 kB)
K. Yu. Gorbunov, V. A. Lyubetsky, “Algorithm of transformation of a graph into another one with minimal cost”, Inform. Primen., 11:1 (2017), 79–89
Citation in format AMSBIB
\by K.~Yu.~Gorbunov, V.~A.~Lyubetsky
\paper Algorithm of transformation of a graph into another one with minimal cost
\jour Inform. Primen.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|