RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






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


Avtomat. i Telemekh., 2018, Issue 12, Pages 124–141 (Mi at15225)  

This article is cited in 1 scientific paper (total in 1 paper)

Optimization, System Analysis, and Operations Research

A linear algorithm for restructuring a graph

K. Yu. Gorbunova, V. A. Lyubetskyba

a Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences, Moscow, Russia
b Lomonosov State University, Moscow, Russia

Abstract: We propose an algorithm, linear in both running time and memory, that constructs a sequence of operations that transform any given directed graph with degree of any vertex at most two to any other given graph of the same type with minimal total cost. This sequence is called the shortest one. We allow four standard operations of re-gluing graphs with equal cost and two more additional operations of inserting and deleting a connected section of edges that also have equal cost. We prove that the algorithm finds a minimum with this restriction on the costs.

Keywords: graph, cycle, chain, graph transformation, operation cost, combinatorial problem, optimization on graphs, linear algorithm.

Funding Agency Grant Number
Russian Science Foundation 14-50-00150
This work was carried out at the expense of the Russian Science Foundation, project no. 14-50-00150.


DOI: https://doi.org/10.31857/S000523100002861-1

Full text: PDF file (649 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Automation and Remote Control, 2018, 79:12, 2203–2216

Bibliographic databases:

Presented by the member of Editorial Board: П. Ю. Чеботарев

Received: 31.01.2017

Citation: K. Yu. Gorbunov, V. A. Lyubetsky, “A linear algorithm for restructuring a graph”, Avtomat. i Telemekh., 2018, no. 12, 124–141; Autom. Remote Control, 79:12 (2018), 2203–2216

Citation in format AMSBIB
\Bibitem{GorLyu18}
\by K.~Yu.~Gorbunov, V.~A.~Lyubetsky
\paper A linear algorithm for restructuring a graph
\jour Avtomat. i Telemekh.
\yr 2018
\issue 12
\pages 124--141
\mathnet{http://mi.mathnet.ru/at15225}
\crossref{https://doi.org/10.31857/S000523100002861-1}
\elib{http://elibrary.ru/item.asp?id=36515655}
\transl
\jour Autom. Remote Control
\yr 2018
\vol 79
\issue 12
\pages 2203--2216
\crossref{https://doi.org/10.1134/S0005117918120093}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000453228600009}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85058329733}


Linking options:
  • http://mi.mathnet.ru/eng/at15225
  • http://mi.mathnet.ru/eng/at/y2018/i12/p124

    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

    This publication is cited in the following articles:
    1. Lyubetsky V.A., Lyubetskaya E., Gorbunov K., “Linear Algorithm For a Cyclic Graph Transformation”, Lobachevskii J. Math., 39:9 (2018), 1217–1227  crossref  mathscinet  zmath  isi  scopus
  • Avtomatika i Telemekhanika
    Number of views:
    This page:33
    References:4
    First page:4

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