\input zb-basic
\input zb-ioport
\iteman{io-port 04018804}
\itemau{Dushin, B.I.; Babushkin, A.I.}
\itemti{On the determination of the optimal combination of two priority rules in the travelling salesman problem.}
\itemso{Kibernetika 1985, No.4, 122-124 (1985).}
\itemab
For the given two orderings $\Pi\sb 1$ and $\Pi\sb 2$ of vertices of a weighted graph the authors consider a rule for constructing a new ordering $\Pi$. They show that using this rule it is possible to construct shortest paths in time $O(n\sp 3)$. If $\Pi\sb 1(i)=\Pi\sb 2(n- i-1)$ and $\Pi\sb 1$ and $\Pi\sb 2$ are allowed to be changed dynamically during the construction of $\Pi$ then by using the rule Hamiltonian cycles of minimal length can be constructed.
\itemrv{M.Frumkin}
\itemcc{}
\itemut{priority rules; travelling salesman; weighted graph; shortest paths}
\itemli{}
\end