РАЗРЕШИМОСТЬ ОБОБЩЕННОЙ ЗАДАЧИ КОММИВОЯЖЕРА В КЛАССЕ КВАЗИ- И ПСЕВДОПИРАМИДАЛЬНЫХ МАРШРУТОВ

科研成果: Article

摘要

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
源语言Russian
页(从-至)280-291
页数12
期刊Труды института математики и механики УрО РАН
23
3
DOI
Published - 2017

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

引用此