RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
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


Inform. Primen., 2017, Volume 11, Issue 1, Pages 79–89 (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

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).


DOI: https://doi.org/10.14357/19922264170107

Full text: PDF file (259 kB)
References: PDF file   HTML file

Document Type: Article
Received: 26.04.2016

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{http://elibrary.ru/item.asp?id=29159457}


Linking options:
  • http://mi.mathnet.ru/eng/ia461
  • http://mi.mathnet.ru/eng/ia/v11/i1/p79

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Информатика и её применения
    Number of views:
    This page:99
    Full text:20
    References:8
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018