Результаты исследований: Вклад в журнал › Статья › Рецензирование
We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with n nodes and k clusters, optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4(l)n(3)) and O(2(l)k(l+4)n(3)), respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint H
Переведенное название | Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours |
---|---|
Язык оригинала | Русский |
Страницы (с-по) | 280-291 |
Число страниц | 12 |
Журнал | Труды института математики и механики УрО РАН |
Том | 23 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - 2017 |
ID: 8556474