04189491

j

04189491 Michalski, M. On a class of polynomially solvable travelling salesman problems. Zastosow. Mat. 19, No.3-4, 531-539 (1987). 1987 EN polynomial algorithm travelling salesman skew orderable networks 4- vertex cycles Summary: We introduce a class of so-called skew orderable networks. Roughly speaking one can assign positive integers to the vertices of a skew orderable network G in such a way that the assignment, called an ordering function for G, reflects certain structural properties of 4-vertex cycles of G. It is shown that finding a shortest Hamiltonian cycle in a skew orderable network is nothing else but constructing an ordering function, which in turn can be obtained in polynomial time with respect to the number of vertices.