A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n2 Pairwise Distances in n2 Steps for the Sequencing Problem: II. Algorithm

A new uniform algorithm based on sequential removal of redundancy from inputs is proposed to solve the turnpike and beltway problems. For error-free inputs that simulate experimental data with high accuracy, the size of inputs decreases from O(n(2)) to O(n), which permits one to eliminate exhaustive search almost completely and reconstruct sequences in n(2) steps. Computational experiments show high efficiency of the algorithm for both the turnpike and beltway cases, with the reconstruction time for sequences of lengths up to several thousand elements being within 1 second on a modern PC.