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 contribution||An exact algorithm with linear complexity for a problem of visiting megalopolises|
|Number of pages||9|
|Journal||Труды института математики и механики УрО РАН|
|Publication status||Published - 2015|
- 27.00.00 MATHEMATICS
Level of Research Output
- VAK List