Re: Finding a minimal cost tree for the network
- From: Patricia Shanahan <patricia_shanahan@xxxxxxxxxxxxx>
- Date: Sat, 30 Apr 2005 15:18:24 GMT
Bob wrote:
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.
Try a google search for:
rectilinear distance minimum steiner tree
It produced several useful-looking hits.
In particular:
http://portal.acm.org/citation.cfm?id=238997.239033
@article{239033,
author = {Joseph L. Ganley and James P. Cohoon},
title = {Rectilinear Steiner trees on a checkerboard},
journal = {ACM Trans. Des. Autom. Electron. Syst.},
volume = {1},
number = {4},
year = {1996},
issn = {1084-4309},
pages = {512--522},
doi = {http://doi.acm.org/10.1145/238997.239033},
publisher = {ACM Press},
address = {New York, NY, USA},
}
Patricia
.
- Prev by Date: JMF massive memory leak
- Next by Date: Need a large amount of memory!
- Previous by thread: JMF massive memory leak
- Next by thread: Need a large amount of memory!
- Index(es):
Relevant Pages
|
