Computer Solutions of the Traveling Salesman Problem

Mapping DNA by stochastic relaxation: schedule for optimal annealing

The analysis of the various cooling schedules for the simulated annealing algorithm is made towards the restriction map construction. Algorithm behaviour under control of three different cost functions is considered and the discrete cost function is found to handle successfully experimental data with realistic error sizes. A program using this function has been derived from the algorithm to construct linear and circular DNA maps.

Parallel Distributed Approaches to Combinatorial Optimization: Benchmark Studies on Traveling Salesman Problem

We present and summarize the results from 50-, 100-, and 200-city TSP benchmarks presented at the 1989 Neural Information Processing Systems (NIPS) postconference workshop using neural network, elastic net, genetic algorithm, and simulated annealing approaches. These results are also compared with a state-of-the-art hybrid approach consisting of greedy solutions, exhaustive search, and simulated annealing.

Graph theory applied to optimal connectivity in computer networks

This is a report on some of the research that has been carried out in applying graph theoretical results to communications networks. The networks that we wish to investigate here consist of computers at various sites which are linked together by telecommunications circuits.

Many of the results of graph theory may be applied to such networks; we will restrict ourselves to the consideration of connectivity. In designing a computer communications network, it is desirable to provide good connectivity among all sites at reasonable cost. For this reason, extremes like the fully-connected network (too expensive) and the star network (only as reliable as its center) are usually not considered. The connectivity constraints or reliability measures can be stated in different ways, and analytic techniques have been developed for some of these measures. Further, procedures for the synthesis of well-connected networks have also been invented.

The reliability of communications networks is an important issue in their design and operation. Telecommunications circuits become noisy and unusable, and the communications computers may also fail. This report is a survey of that part of applied graph theory which is useful in the study of the connectivity of communications networks.