An Exact Algorithm with Linear Complexity for a Problem of Visiting Megalopolises / Chentsov A. G.,Khachai M. Yu.,Khachai D. M. // PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS. - 2016. - V. 295, l. 1, 1. - P. S38-S46.

ISSN/EISSN:

0081-5438 / 1531-8605

Type:

Article

Abstract:

A problem of visiting megalopolises with a fixed number of ``entrances{''} and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution, we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.

Author keywords:

traveling salesman problem; NP-hard problem; dynamic programming; precedence relations SALESMAN PROBLEM

DOI:

10.1134/S0081543816090054

Web of Science ID:

ISI:000394441400005

Соавторы в МНС:

Другие поля

Поле	Значение
Month	DEC
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1531-8605
Keywords-Plus	SALESMAN PROBLEM
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	chentsov@imm.uran.ru mkhachay@imm.uran.ru daniil.khachay@gmail.com
ORCID-Numbers	Khachay, Michael/0000-0003-3555-0080
Funding-Acknowledgement	Russian Science Foundation {[}14-11-00109]
Funding-Text	This work was supported by the Russian Science Foundation (project no. 14-11-00109).
Number-of-Cited-References	19
Usage-Count-Last-180-days	1
Usage-Count-Since-2013	2
Journal-ISO	Proc. Steklov Inst. Math.
Doc-Delivery-Number	EL2HT