web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000502512
Cybernetics and Systems Analysis   А - 2019 /  Issue (2016, Т. 52, № 3)
Маций О. Б., Морозов А. В., Панишев А. В.
Быстрый алгоритм нахождения 2-фактора минимального веса Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества <$E U prime~symbol <172>~U>, образующих совокупность непересекающихся в вершинах <$E v~symbol <174>~V> простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг.
 https://doi.org/10.1007/s10559-016-9847-9
 Scopus
Бібліографічний опис:
Маций О. Б., Морозов А. В., Панишев А. В. Быстрый алгоритм нахождения 2-фактора минимального веса. Кибернетика и системный анализ. 2016. Т. 52, № 3. С. 154-163. doi: https://doi.org/10.1007/s10559-016-9847-9 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000502512 |
 Cybernetics and Systems Analysis / Issue (2016, 52 (3))
Matsiy O.B.,
Morozov A.V.,
Panishev A.V.
Fast algorithm to find the 2-factor of minimum weight The paper considers the minimization of the sum of weights of edges forming a subset U′ ⊂ U of the set of disjoint simple cycles at vertices υ ϵ V in graph H = (V,U) and covering V. The problem under study (2-f problem) is polynomially solvable in algorithms that are characterized by technical difficulties that hinder the acceleration of computing. The 2-f problem is solved by reducing it to a simpler bipartite case. The result is represented by a perfect matching of bipartite graph corresponding to the solution of the assignment problem, where each circuit of cyclic expansion contains at least three arcs. © 2016, Springer Science+Business Media New York. Keywords: 2-factor, assignment problem, augmenting path, bipartite graph, matching, Algorithms, Combinatorial optimization, 2-factors, Assignment problems, Augmenting path, Bipartite graphs, matching, Graph theory
Cite:
Matsiy O.B.,
Morozov A.V.,
Panishev A.V.
(2016). Fast algorithm to find the 2-factor of minimum weight. Cybernetics and Systems Analysis, 52 (3), 154-163. doi: https://doi.org/10.1007/s10559-016-9847-9 http://jnas.nbuv.gov.ua/article/UJRN-0000502512 [In Russian]. |
PDF