Abstract: In this paper the Hamiltonian Rural Postman Problem is generalization of the Hamiltonian Travelling Salesman Problem is described. The offered modification of a classical method (Little’s method) allows to find exact solution of the Hamilton Rural Postman Problem or to detect that the task is unsolvable.

Keywords: Hamiltonian Rural Postman Problem, Hamiltonian cycle, branch and bound algorithm, Hamiltonian Traveling Salesman Problem

ACM Classification Keywords: G.2.2 - Mathematics of Computing - Discrete Mathematics - Graph Theory - Path and circuit problems

Link:

MODIFIED BRANCH AND BOUND ALGORITHM FOR SOLVING THE HAMILTONIAN RURAL POSTMAN PROBLEM

Andriy Morozov, Anatoliy Panishev

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