Informatika i Ee Primeneniya [Informatics and its Applications]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Inform. Primen.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Informatika i Ee Primeneniya [Informatics and its Applications], 2017, Volume 11, Issue 1, Pages 79–89
DOI: https://doi.org/10.14357/19922264170107
(Mi ia461)
 

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
References:
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.
Keywords: orgraph with chains and cycles; graph transformation; graph transformation with minimal total cost; exact linear algorithm; graph constraint; cost constraint; conditional shortest solution.
Funding agency Grant number
Russian Science Foundation 14-50-00150
The study was supported by the Russian Science Foundation (project No. 14-50-00150).
Received: 26.04.2016
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: 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
\Bibitem{GorLyu17}
\by K.~Yu.~Gorbunov, V.~A.~Lyubetsky
\paper Algorithm of transformation of a graph into another one with minimal cost
\jour Inform. Primen.
\yr 2017
\vol 11
\issue 1
\pages 79--89
\mathnet{http://mi.mathnet.ru/ia461}
\crossref{https://doi.org/10.14357/19922264170107}
\elib{https://elibrary.ru/item.asp?id=29159457}
Linking options:
  • https://www.mathnet.ru/eng/ia461
  • https://www.mathnet.ru/eng/ia/v11/i1/p79
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Информатика и её применения
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024