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

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

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


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




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

Дискретный анализ и исследование операций, 2021, том 28, выпуск 4, страницы 117–124
DOI: https://doi.org/10.33048/daio.2021.28.710 (Mi da1288) 		 
Win-win алгоритм для задачи $(k+1)$-LST/$k$-путевого представления

А. Г. Ключиковa, М. Н. Вялыйabc

a Московский физико-технический институт (гос. университет), Институтский пер., 9, 141701 Долгопрудный, Россия
b Федеральный исследовательский центр «Информатика и управление» РАН, ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
c Национальный исследовательский университет «Высшая школа экономики», Покровский б-р, 11, 109028 Москва, Россия
PDF полного текста (306 kB) Английская версия
Список литературы:
PDF
HTML
DOI: https://doi.org/10.33048/daio.2021.28.710
Аннотация: Описывается win-win алгоритм, строящий за полиномиальное от $|V(G)|$ и $k$ время для любого графа $G$ и любого натурального числа $k$ либо остовное дерево с хотя бы $k+1$ листьями, либо предоставляет путевое представление (path decomposition) ширины не большей $k$. Данный алгоритм оптимален в силу следствия теоремы о путевом представлении [1]. Библиогр. 5.
Ключевые слова: путевое представление, остовное дерево, задача $k$-LST, win-win алгоритм, параметрическая сложность.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 0063-2019-0003
Работа второго автора выполнена при поддержке Программы фундаментальных исследований НИУ ВШЭ, а также в рамках государственного задания ФИЦ ИУ РАН (проект № 0063–2019–0003).
Статья поступила: 12.04.2021
Переработанный вариант: 02.08.2021
Принята к публикации: 03.08.2021
Английская версия:
Journal of Applied and Industrial Mathematics, 2021, Volume 15, Issue 4, Pages 627–630
DOI: https://doi.org/10.1134/S1990478921040062
Тип публикации: Статья
УДК: 519.178
Образец цитирования: А. Г. Ключиков, М. Н. Вялый, “Win-win алгоритм для задачи $(k+1)$-LST/$k$-путевого представления”, Дискретн. анализ и исслед. опер., 28:4 (2021), 117–124; J. Appl. Industr. Math., 15:4 (2021), 627–630
Цитирование в формате AMSBIB
\RBibitem{KlyVya21}
\by А.~Г.~Ключиков, М.~Н.~Вялый
\paper Win-win алгоритм для задачи $(k+1)$-LST/$k$-путевого представления
\jour Дискретн. анализ и исслед. опер.
\yr 2021
\vol 28
\issue 4
\pages 117--124
\mathnet{http://mi.mathnet.ru/da1288}
\crossref{https://doi.org/10.33048/daio.2021.28.710}
\transl
\jour J. Appl. Industr. Math.
\yr 2021
\vol 15
\issue 4
\pages 627--630
\crossref{https://doi.org/10.1134/S1990478921040062}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da1288
  • https://www.mathnet.ru/rus/da/v28/i4/p117
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:267
    PDF полного текста:134
    Список литературы:66
    Первая страница:3
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2026