Быстрый алгоритм нахождения 2-фактора минимального веса

Быстрый алгоритм нахождения 2-фактора минимального веса

Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудн...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2016
Автори: Маций, О.Б., Морозов, А.В., Панишев, А.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:Кибернетика и системный анализ
Теми:
Системный анализ
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/133690
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-133690
record_format dspace
spelling irk-123456789-1336902018-06-06T03:03:26Z Быстрый алгоритм нахождения 2-фактора минимального веса Маций, О.Б. Морозов, А.В. Панишев, А.В. Системный анализ Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг. Розглянуто задачу мінімізації у графі H = (V, U) суми ваг ребер підмножини U' ⊂ U, що утворюють сукупність простих циклів, які не перетинаються у вершинах v ∈ V і покривають V. Розглянута задача (задача 2-f) може бути поліноміально розв’язана алгоритмами, які характеризуються технічними труднощами, що перешкоджають прискоренню процесу обчислень. Розв’язок задачі 2-f знаходиться зведенням її до більш простого двочасткового випадку. Результат представлено досконалою паросполукою двочасткового графа, відповідною розв’язку задачі про призначення, у цикловому розвиненні якої кожний контур містить не менше трьох дуг. The paper considers the minimization of the sum of weights of edges forming a subset of the set of disjoint simple cycles at the vertices in the graph H = (V, U) and cover V. This problem (2-f problem) is solvable in polynomial algorithms, which are characterized by technical difficulties that hinder accelerate computing. The solution of 2-f is reducing it to a simple bipartite case. The desired result is represented by a perfect matching of a bipartite graph corresponding to the solution of the assignment problem, in which each expansion cycle circuit comprises at least three arcs. 2016 Article Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/133690 519.161 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Системный анализ
Системный анализ
spellingShingle Системный анализ
Системный анализ
Маций, О.Б.
Морозов, А.В.
Панишев, А.В.
Быстрый алгоритм нахождения 2-фактора минимального веса
Кибернетика и системный анализ
description Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг.
format Article
author Маций, О.Б.
Морозов, А.В.
Панишев, А.В.
author_facet Маций, О.Б.
Морозов, А.В.
Панишев, А.В.
author_sort Маций, О.Б.
title Быстрый алгоритм нахождения 2-фактора минимального веса
title_short Быстрый алгоритм нахождения 2-фактора минимального веса
title_full Быстрый алгоритм нахождения 2-фактора минимального веса
title_fullStr Быстрый алгоритм нахождения 2-фактора минимального веса
title_full_unstemmed Быстрый алгоритм нахождения 2-фактора минимального веса
title_sort быстрый алгоритм нахождения 2-фактора минимального веса
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2016
topic_facet Системный анализ
url http://dspace.nbuv.gov.ua/handle/123456789/133690
citation_txt Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT macijob bystryjalgoritmnahoždeniâ2faktoraminimalʹnogovesa
AT morozovav bystryjalgoritmnahoždeniâ2faktoraminimalʹnogovesa
AT paniševav bystryjalgoritmnahoždeniâ2faktoraminimalʹnogovesa
first_indexed 2023-10-18T21:06:25Z
last_indexed 2023-10-18T21:06:25Z
_version_ 1796151941207687168

Схожі ресурси