TitleThe shortest network problem
CreditsGraham, Ronald L.
PublisherUniversity Video Communications
Copyright HolderComputer History Museum
DescriptionFrom University Video Communications' catalog:
"The efficient routing of telephone messages between cities is just one of many situations in which the Steiner problem often arises. This problem asks for the shortest network of line segments to interconnect a set of given points. It appears, for example, in the design of highway systems, oil pipelines, air conditioning systems, and integrated circuits on silicon chips. This overview of the Steiner problem provides an introduction to NP-completeness, a fundamental concept in theoretical computer science."