given a connected graph and a number N, select N vertices in the graph so that the size of the Steiner tree (Steiner tree problem on graphs) spanning the selected vertices is maximized. (by definition, a Steiner tree minimizes its size, so this is a maximum-minimum problem.) the size of a Steiner tree is sum of the weights of all its edges. if unweighted edges, let every edge have unit weight.
if N=2, then the size of the maximum Steiner tree is graph diameter. for larger N, this generalizes graph diameter: find the N points farthest away from each other.
for an adventure game exploring a graph, these are where the treasures are hidden.
what is the computational complexity of this problem? solving the Steiner tree problem on graphs just once is NP-complete; now we are solving it binomial(number of graph vertices, N) times.
No comments:
Post a Comment