Artifact Details

Title

The shortest network problem

Catalog Number

102724535

Type

Moving image

Date

1988-10-28

Credits

Graham, Ronald L.

Publisher

University Video Communications

Duration

00:53:41

Format

Betacam SP

Copyright Holder

Computer History Museum

Description

From 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."

Category

Lecture

Collection Title

University Video Communications lectures

Series Title

Distinguished Lecture Series : Theoretical Computer Science

Credit

Gift of University Video Communications

Lot Number

X6636.2013