Skip to main content

On Sale: GamesAssetsToolsTabletopComics
Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Problem 16: Steiner Tree

A topic by procmeal games created Sep 06, 2022 Views: 70
Viewing posts 1 to 1
HostSubmitted

The inputs are a graph, G, and a list of terminal vertices.  The goal is to create a subtree that spans all the terminal vertices.  The non-terminal vertices may or may not be included in the subtree.  There will always be such a subtree.

This is similar to minimal spanning tree, but it's harder because not all vertices have to be included.  It's permitted to have weighted graphs for this problem, in which case you should look for the minimum tree that spans all the terminal vertices.

Here's a video: https://youtu.be/BG4vAoV5kWw