RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

А. В. Смирнов

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

Аннотация: В статье рассматривается задача о наибольшем кратном потоке в сети произвольной натуральной кратности $k$. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение $k$ связанных дуг, согласованных между собой. Задаются правила построения сети.
Вводится понятие делимой сети и ряд связанных определений. Отмечается важная особенность делимых сетей – возможность разделить их на $k$ частей, согласованных на связанных дугах кратных и мультидуг, таким образом, что каждая часть является обычной транспортной сетью.
Основным результатом статьи является выделение следующих подклассов задачи о наибольшем кратном потоке в делимой сети.
  • Делимая сеть с ограничениями на мультидуги. Если в $k-1$ части делимой сети имеется только одна вершина, являющаяся концом мультидуги, то задача о наибольшем потоке полиномиально разрешима.
  • Делимая сеть со слабыми ограничениями на мультидуги. Если в $s$ частях делимой сети ($1\leq s<k-1$) имеется только одна вершина, являющаяся концом мультидуги, а в остальных частях таких вершин несколько, то размерность задачи о наибольшем кратном потоке может быть понижена до $k-s$.
  • Делимая сеть параллельной структуры. Пусть компонента делимой сети, состоящая из всех кратных дуг, может быть разделена на субкомпоненты, содержащие ровно по одной вершине-началу мультидуги. Пусть при этом каждая пара субкомпонент пересекается только в источнике сети $x_0$. Если $k=2$, то задача о максимальном кратном потоке разрешима за полиномиальное время. Если $k\geq3$, то задача $NP$-полна.

Для каждого из полиномиальных подклассов получены алгоритмы. Также сформулирован алгоритм понижения размерности задачи для делимой сети со слабыми ограничениями на мультидуги.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-07-03038 A


DOI: https://doi.org/10.18255/1818-1015-2015-4-533-545

Полный текст: PDF файл (573 kB)
Список литературы: PDF файл   HTML файл

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

Тип публикации: Статья
УДК: 519.179.2, 519.854.3
Поступила в редакцию: 10.07.2015

Образец цитирования: А. В. Смирнов, “Задача о наибольшем кратном потоке в делимой сети и ее частные случаи”, Модел. и анализ информ. систем, 22:4 (2015), 533–545

Цитирование в формате AMSBIB
\RBibitem{Smi15}
\by А.~В.~Смирнов
\paper Задача о наибольшем кратном потоке в делимой сети и ее частные случаи
\jour Модел. и анализ информ. систем
\yr 2015
\vol 22
\issue 4
\pages 533--545
\mathnet{http://mi.mathnet.ru/mais458}
\crossref{https://doi.org/10.18255/1818-1015-2015-4-533-545}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3418472}
\elib{http://elibrary.ru/item.asp?id=24273053}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais458
  • http://mi.mathnet.ru/rus/mais/v22/i4/p533

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Смирнов, “Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы”, Модел. и анализ информ. систем, 23:4 (2016), 466–478  mathnet  crossref  mathscinet  elib
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:72
    Полный текст:12
    Литература:11

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019