Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

CLASSROOM NOTES: A nod to the traveling salesman

Bruce Torrence
Organization: Randolph-Macon College
Department: Department of Mathematics
Journal / Anthology

Mathematica in Education and Research
Year: 2006
Volume: 11
Issue: 4

The traveling salesman problem is perhaps the best known of the NP-complete problems. These are the most difficult problems in the class known as NP (nondeterministic polynomial time), where no efficient, or polynomial time, algorithm has been discovered to solve one. As such, the traveling salesman problem makes an excellent introduction to the concept of combinatorial complexity. In this note we will show how the Combinatorica package and some simple greedy algorithms can be easily harnessed to bring these concepts into the classroom.

*Mathematics > Discrete Mathematics > Combinatorics
*Wolfram Technology > Application Packages