RUS  ENG
Полная версия
ЖУРНАЛЫ // Моделирование и анализ информационных систем // Архив

Модел. и анализ информ. систем, 2015, том 22, номер 4, страницы 533–545 (Mi mais458)

Эта публикация цитируется в 2 статьях

Задача о наибольшем кратном потоке в делимой сети и ее частные случаи

А. В. Смирнов

Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14, г. Ярославль, 150000 Россия

Аннотация: В статье рассматривается задача о наибольшем кратном потоке в сети произвольной натуральной кратности $k$. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение $k$ связанных дуг, согласованных между собой. Задаются правила построения сети.
Вводится понятие делимой сети и ряд связанных определений. Отмечается важная особенность делимых сетей – возможность разделить их на $k$ частей, согласованных на связанных дугах кратных и мультидуг, таким образом, что каждая часть является обычной транспортной сетью.
Основным результатом статьи является выделение следующих подклассов задачи о наибольшем кратном потоке в делимой сети.
Для каждого из полиномиальных подклассов получены алгоритмы. Также сформулирован алгоритм понижения размерности задачи для делимой сети со слабыми ограничениями на мультидуги.

Ключевые слова: кратные сети, кратные потоки, делимые сети, $NP$-полнота, полиномиальный алгоритм.

УДК: 519.179.2, 519.854.3

Поступила в редакцию: 10.07.2015

DOI: 10.18255/1818-1015-2015-4-533-545



Реферативные базы данных:


© МИАН, 2024