The Steiner Tree Problem

All,

Any one from this group can help me to solve this problem please!!!

Thanks
Bob.

The cost for a communication line between two stations is proportional
to the length of the line. The cost for conventional minimal spanning
trees of a set of stations can often be cut by introducing "phantom"
stations and then constructing a new Steiner tree. This device allows
costs to be cut by up to 13.4% (= 1- sqrt(3/4)). Moreover, a network
with n stations never requires more than n-2 points to construct the
cheapest Steiner tree. Two simple cases are shown in Figure 1.
For local networks, it often is necessary to use rectilinear or
"checker-board" distances, instead of straight Euclidean lines.
Distances in this metric are computed as shown in Figure 2.

Suppose you wish to design a minimum costs spanning tree for a local
network with 9 stations. Their rectangular coordinates are: a(0,15),
b(5,20), c(16,24), d(20,20), e(33,25), f(23,11), g(35,7), h(25,0)
i(10,3). You are restricted to using rectilinear lines. Moreover, all
"phantom" stations must be located at lattice points (i.e., the
coordinates must be integers). The cost for each line is its length.

Find a minimal cost tree for the network.

.

Relevant Pages

  • Re: Finding a minimal cost tree for the network
    ... The cost for a communication line between two stations is proportional ... The cost for conventional minimal spanning ... stations and then constructing a new Steiner tree. ...
    (comp.lang.java.programmer)
  • Finding a minimal cost tree for the network
    ... The cost for a communication line between two stations is proportional ... stations and then constructing a new Steiner tree. ... Find a minimal cost tree for the network. ...
    (sci.math)
  • Re: Building railings at MRT open platforms
    ... Any idiot architect can design one. ... to see who can create the cheapest and most cost effective barrier design. ... barriers for 36 stations and trains will be running 18 hours a day. ... These product materials are ...
    (soc.culture.singapore)
  • Re: Building railings at MRT open platforms
    ... as barrier in all open platform mrt stations into advertising board and help ... SMRT would have to decide if it is worth the cost but if it can help to stop ... wall at "high suicide mrt stations". ...
    (soc.culture.singapore)
  • Re: Building railings at MRT open platforms
    ... as barrier in all open platform mrt stations into advertising board and help ... SMRT would have to decide if it is worth the cost but if it can help to stop ... wall at "high suicide mrt stations". ...
    (soc.culture.singapore)