Проекты за года
Аннотация
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 |
Предметные области WoS
- Математика, Прикладная
ГРНТИ
- 27.00.00 МАТЕМАТИКА
Уровень публикации
- Перечень ВАК
Проекты
- 1 Активно
-
Научная лаборатория «Лаборатория оптимального раскроя промышленных материалов и оптимальных маршрутных технологий»
Петунин, А. А., Ченцов, П. А., Ченцов, А. Г., Сесекин, А. Н., Верхотуров, М. А., Картак, В. М., Fisher, A., Scheithauer, G., Мясогутов, М., Панюкова, Т. А., Кошелева, М. С., Полищук, Е. Г., Шипачёва, Е. Н., Репницкий, В. Б., Захарова, Г. Б., Полевов, А. В., Кротов, В. И., Галкин, И. С., Березин, И. М., Чернухин, В. И., Таваева, А. Ф., Фатехрад, М., Асанбеков, К. А., Панюков, А. В., Котел, Н. С., Уколов, С. С., Миронов, К. В., Салий, Я. В., Попов, В. Ю., Хачай, М. Ю., Иванко, Е. Е. & Савчук, А.
12/12/2013 → …
Проект: Исследование › Научная лаборатория