An algorithm with estimation for the travelling salesman maximum problem. (Russian) Zbl 0569.90089

Serdyukov, A. I.

Upr. Sist. 25, 80-86 (1984).

The author proposes an approximate algorithm for the construction of a Hamiltonian cycle of maximal length in a graph G. The accuracy of the algorithm equals 3/4 and its time complexity equals \(O((V(G))^ 4)\). The algorithm successively reconfigurates a spanning set of simple loops in G into a Hamiltonian cycle.

Reviewer: M.Frumkin

MSC:

90C35	Programming involving graphs or networks
05C35	Extremal problems in graph theory

Keywords:

estimation; travelling salesman; approximate algorithm; Hamiltonian cycle of maximal length; spanning set of simple loops