Steiner problem

From Glossary

Jump to: navigation, search

Find a subgraph of a graph, say LaTeX: \textstyle G' = [V',E'], such that LaTeX: V' contains LaTeX: V^* (a specified subset of nodes), and LaTeX: \textstyle \sum \{c(e): e \in E'\} is minimized. It is generally assumed LaTeX: \textstyle c \ge 0. When LaTeX: \textstyle |V^*|=2, this is the shortest path problem. When LaTeX: \textstyle |V^*|=|V|, this is the (minimum) spanning tree problem.

Personal tools