In the middle 1930s computer science was yet a not well defined academic discipline. Actually, fundamental concepts, such as ‘algorithm’, or ‘computational problem’, has been formalized just some year before. In these years the Austrian mathematician Karl Menger invited the research community to consider from a mathematical point of view the following problem taken from the every day life. A traveling salesman has to visit exactly once each one of a list of m cities and then return to the home city. He knows the cost of traveling from any city i to any other city j. Thus, which is the tour of least possible cost the.
