Steiner Trees

Ice Roads #

The Minimal Spanning Trees activity explored techniques for finding efficient networks between points. Steiner trees are another way to approach the same problem, and they can be used to find even more efficient networks.

This is another tough problem from computer science, converted into an activity which is easy to explain, with variations suitable for higher-level students.

Activity description (PDF) #

• Instructions for Steiner Trees activity (English)

Translations and other versions #

• Chinese language version
• Polish language version
• Slovenian language version

Related Resources #

• Wikipedia: Steiner Tree Problem
• The Mathmaniacs web site has a similar activity (lesson 14)

Curriculum #

Great Principles of Computer Science #

• Computation