Finding a minimal cost tree for the network

Discussion in 'Java' started by Bob, Apr 30, 2005.

  1. Bob

    Bob Guest

    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.
     
    Bob, Apr 30, 2005
    #1
    1. Advertising

  2. 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
     
    Patricia Shanahan, Apr 30, 2005
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kal
    Replies:
    1
    Views:
    9,529
    Kevin Spencer
    Jun 21, 2004
  2. Jane Davis

    Network Service account over network

    Jane Davis, Jun 22, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    451
    Kevin Spencer
    Jun 22, 2005
  3. Bill Volk
    Replies:
    1
    Views:
    3,154
    Bill Volk
    Jul 2, 2003
  4. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,128
  5. kin
    Replies:
    0
    Views:
    918
Loading...

Share This Page