Loading [MathJax]/jax/output/SVG/config.js
Дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

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

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


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




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

Дискретная математика, 2019, том 31, выпуск 4, страницы 20–37
DOI: https://doi.org/10.4213/dm1526 (Mi dm1526) 		 
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ

Р. М. Колпаковab, М. А. Посыпкинb

a МГУ им. М.В.Ломоносова
b Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН
PDF полного текста (530 kB) Список цитирования (2)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/dm1526
Аннотация: Рассматривается легко реализуемая на практике стратегия распараллеливания при решении задачи о сумме подмножеств методом ветвей и границ, называемая рекурсивной стратегией распараллеливания. Сравниваются два различных варианта этой стратегии: фронтальный и сбалансированный. На примере частного случая задачи о сумме подмножеств показано, что сбалансированный вариант является более эффективным, чем фронтальный вариант. Более того, показано, что для рассматриваемого частного случая задачи о сумме подмножеств сбалансированный вариант является оптимальным по времени.
Ключевые слова: метод ветвей и границ, параллельная вычислительная сложность, задача о сумме подмножеств.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-07-00566 А
Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант 18-07-00566 А).
Статья поступила: 25.06.2019
Переработанный вариант поступил: 06.09.2019
Англоязычная версия:
Discrete Mathematics and Applications, 2020, Volume 30, Issue 5, Pages 313–325
DOI: https://doi.org/10.1515/dma-2020-0028
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2
Образец цитирования: Р. М. Колпаков, М. А. Посыпкин, “Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ”, Дискрет. матем., 31:4 (2019), 20–37; Discrete Math. Appl., 30:5 (2020), 313–325
Цитирование в формате AMSBIB
\RBibitem{KolPos19}
\by Р.~М.~Колпаков, М.~А.~Посыпкин
\paper Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ
\jour Дискрет. матем.
\yr 2019
\vol 31
\issue 4
\pages 20--37
\mathnet{http://mi.mathnet.ru/dm1526}
\crossref{https://doi.org/10.4213/dm1526}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4043281}
\elib{https://elibrary.ru/item.asp?id=45175916}
\transl
\jour Discrete Math. Appl.
\yr 2020
\vol 30
\issue 5
\pages 313--325
\crossref{https://doi.org/10.1515/dma-2020-0028}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000582465000004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85094928036}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm1526
  • https://doi.org/10.4213/dm1526
  • https://www.mathnet.ru/rus/dm/v31/i4/p20
    • Эта публикация цитируется в следующих 2 статьяx:
    1. Roman Kolpakov, “The comparing analysis of two parallelization schemes for computations with round memory”, Discrete Math. Algorithm. Appl., 17:01 (2025)  crossref
    2. Roman Kolpakov, Mikhail Posypkin, “Lower time bounds for parallel solving of the subset sum problem by a dynamic programming algorithm”, Concurrency and Computation, 36:18 (2024)  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:424
    PDF полного текста:72
    Список литературы:56
    Первая страница:22
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025