|
Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов
М. Ю. Хачай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), полиномиально разрешимый подкласс, квазипирамидальный маршрут, псевдопирамидальный маршрут.
Поступила в редакцию: 29.05.2017
Образец цитирования:
М. Ю. Хачай, Е. Д. Незнахина, “Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов”, Тр. ИММ УрО РАН, 23, № 3, 2017, 280–291
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1458 https://www.mathnet.ru/rus/timm/v23/i3/p280
|
Статистика просмотров: |
Страница аннотации: | 274 | PDF полного текста: | 56 | Список литературы: | 41 | Первая страница: | 13 |
|