ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ

Translated title of the contribution: An exact algorithm with linear complexity for a problem of visiting megalopolises

Research output: Contribution to journalArticlepeer-review

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.
Translated title of the contributionAn exact algorithm with linear complexity for a problem of visiting megalopolises
Original languageRussian
Pages (from-to)309-317
Number of pages9
JournalТруды института математики и механики УрО РАН
Volume21
Issue number3
Publication statusPublished - 2015

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Fingerprint

Dive into the research topics of 'An exact algorithm with linear complexity for a problem of visiting megalopolises'. Together they form a unique fingerprint.

Cite this