Minimum Cost Reliability Constrained Spanning Trees
The
minimum cost reliability constrained spanning tree problem arises in
communication networks: We are given a set of N stations in the plane that can
communicate with each other. We now want to connect the stations, the cost of a
connection might be modeled by the distance of the stations and the reliability
of a connection by its fault probability. We now want to compute a minimum cost
connection (spanning tree) such that its total fault probability is beyound a
given limit. This problem can be modeled as a constrained minimum spanning
tree problem and thus be solved using the CNOP package.
Minimum Cost Spannig Tree (Costs are euclidean distances, error
probability corresponds to width of edges, all possible edges are shown in
yellow)
Minimum Cost Reliability Constrained Spanning Tree
gmx.de