×

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

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
PDF BibTeX XML Cite