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

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

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



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






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


Модел. и анализ информ. систем, 2016, том 23, номер 4, страницы 466–478 (Mi mais515)  

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

Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы

А. В. Смирнов

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

Аннотация: Рассматривается задача целочисленного сбалансирования четырехмерной матрицы. В исходной вещественной матрице элементы внутренней части (все четыре индекса больше нуля) просуммированы по каждому направлению и каждому плоскому и трехмерному сечению матрицы, а также найдена общая сумма. Данные суммы размещаются в элементах матрицы, у которых один или несколько индексов равны нулю (в соответствии с направлениями суммирования). Ищется целочисленная матрица той же структуры, получаемая из исходной заменой элементов на округления до целого сверху или целого снизу. При этом элемент с четырьмя нулевыми индексами получается по обычным правилам округления.
В статье рассматривается также задача о наибольшем кратном потоке в сети произвольной натуральной кратности $k$. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение $k$ связанных дуг, согласованных между собой. Задаются правила построения сети. Вводится понятие делимой сети и ряд связанных определений.
Определяются общие принципы сведения задачи целочисленного сбалансирования $l$-мерной матрицы ($l\geq3$) к задаче о максимальном потоке в делимой кратной сети кратности $k$.
Задаются правила сведения четырехмерной задачи сбалансирования к задаче о наибольшем потоке в сети кратности 5. Для этой сети формулируется алгоритм нахождения максимального потока, удовлетворяющего условиям разрешимости задачи сбалансирования.

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

DOI: https://doi.org/10.18255/1818-1015-2016-4-466-478

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

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

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

Образец цитирования: А. В. Смирнов, “Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы”, Модел. и анализ информ. систем, 23:4 (2016), 466–478

Цитирование в формате AMSBIB
\RBibitem{Smi16}
\by А.~В.~Смирнов
\paper Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы
\jour Модел. и анализ информ. систем
\yr 2016
\vol 23
\issue 4
\pages 466--478
\mathnet{http://mi.mathnet.ru/mais515}
\crossref{https://doi.org/10.18255/1818-1015-2016-4-466-478}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3549347}
\elib{http://elibrary.ru/item.asp?id=26561564}


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

    ОТПРАВИТЬ: 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. А. В. Смирнов, “Задача о кратчайшем пути в кратном графе”, Модел. и анализ информ. систем, 24:6 (2017), 788–801  mathnet  crossref  elib
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:49
    Полный текст:8
    Литература:8

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