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

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

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



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Труды Института математики и механики УрО РАН, 2017, том 23, номер 3, страницы 280–291
DOI: https://doi.org/10.21538/0134-4889-2017-23-3-280-291
(Mi timm1458)
 

Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов

М. Ю. Хачайabc, Е. Д. Незнахинаca

a Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
b Омский государственный технический университет
c Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Список литературы:
Аннотация: В работе изучается общая постановка обобщенной задачи коммивояжера (GTSP), в которой требуется построить кратчайший циклический маршрут, посещающий каждый элемент фиксированного разбиения множества вершин заданного взвешенного графа (именуемый кластером или мегаполисом) в единственной вершине. Обобщив классическое понятие пирамидального маршрута и введя в рассмотрение квази- и псевдопирамидальные маршруты для задачи GTSP, мы показали, что оптимальный $l$-квазипирамидальный и $l$-псевдопирамидальный маршруты в произвольной постановке задачи на $n$ вершинах и $k$ кластерах могут быть построены за время $O(4^l n^3)$ и $O(2^lk^{l+4}n^3)$ соответственно. Как следствие показано, что задача GTSP принадлежит классу FPT относительно параметризаций, задаваемых такими типами маршрутов. Кроме того, обоснована полиномиальная разрешимость геометрического подкласса задачи, известного в литературе как GTSP-GC, произвольная постановка которого стеснена дополнительным ограничением $H\leq 2$ на высоту решетки, определяющей кластеры.
Ключевые слова: обобщенная задача коммивояжера (GTSP), полиномиально разрешимый подкласс, квазипирамидальный маршрут, псевдопирамидальный маршрут.
Финансовая поддержка Номер гранта
Российский научный фонд 14-11-00109
Исследования поддержаны Российским научным фондом, грант 14-11-00109.
Поступила в редакцию: 29.05.2017
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16 + 519.85
MSC: 90C27, 90C59, 90B06
Образец цитирования: М. Ю. Хачай, Е. Д. Незнахина, “Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов”, Тр. ИММ УрО РАН, 23, № 3, 2017, 280–291
Цитирование в формате AMSBIB
\RBibitem{KhaNez17}
\by М.~Ю.~Хачай, Е.~Д.~Незнахина
\paper Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов
\serial Тр. ИММ УрО РАН
\yr 2017
\vol 23
\issue 3
\pages 280--291
\mathnet{http://mi.mathnet.ru/timm1458}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-3-280-291}
\elib{https://elibrary.ru/item.asp?id=29938020}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm1458
  • https://www.mathnet.ru/rus/timm/v23/i3/p280
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:274
    PDF полного текста:56
    Список литературы:41
    Первая страница:13
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024