Avtomat. i Telemekh., 2018, Issue 12, Pages 124–141
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
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.
graph, cycle, chain, graph transformation, operation cost, combinatorial problem, optimization on graphs, linear algorithm.
|Russian Science Foundation
|This work was carried out at the expense of the Russian Science Foundation, project no. 14-50-00150.
PDF file (649 kB)
First page: PDF file
Automation and Remote Control, 2018, 79:12, 2203–2216
Presented by the member of Editorial Board: П. Ю. Чеботарев
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
\by K.~Yu.~Gorbunov, V.~A.~Lyubetsky
\paper A linear algorithm for restructuring a graph
\jour Avtomat. i Telemekh.
\jour Autom. Remote Control
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Lyubetsky V.A., Lyubetskaya E., Gorbunov K., “Linear Algorithm For a Cyclic Graph Transformation”, Lobachevskii J. Math., 39:9 (2018), 1217–1227
|Number of views:|