Abstract: Searching for cycling routes of minimum cost is an urgent task of transport nets designing, traffic flows
routing, etc. Each locality, transport node can be the vertex of the graph, and each cut line, linking localities, − the
edge of the graph. The edge’s cost represents distance, repair cost, channel bandwidth, circuit resistance, etc.
If closed route reaches all vertexes of the graph exactly once, it is called Hamiltonian cycle (HC), and the task of
searching for minimum cost is the Hamiltonian Traveling Salesman’s Problem (HTSP). HTSP is NP-hard and not
always has a solution Майника, 1981. Algorithms delivering optimum to HTSP are described as an exhaustive
search reduction.
If restriction of visiting only once every vertex is taken off, then such task can be called Common Traveling
Salesman Problem (CTSP). Besides completeness of the route is an additional restriction for this task. CTSP
seems the generalization of HTSP Бондаренко, 2004. For every linked graph always the CTSP’s set of
solutions is not empty, and it allows using approximate algorithms and heuristics. The authors have no data about
exact methods, bringing optimum of closed CTSP.
This article offers exact algorithm of CTSP solution, bringing the cycle of minimum cost, which includes all
vertexes of the graph at least once and contains the less number of edges.

Keywords: TSP, Traveling Salesman Problem, Hamiltonian cycle, closed route, optimal route, exact algorithm.

ACM Classification Keywords: Algorithms, Theory.

Link:

CYCLE ROUTES OPTIMIZATION FOR NOT FULL GRAPH

Anatoly Panishev, Anton Levchenko

http://foibg.com/ibs_isc/ibs-19/ibs-19-p54.pdf