## Minimum Spanning Tree (Telecommunications) Homework Problem

Mike Bartolacci mrb24@psu.edu

8 May 2000

Acme Distribution Inc. has 11 sales offices throughout the country that it wants to link via a wide area network (WAN). The wide area network is to be structured such that a high capacity "backbone" will be used to link the various sites. Because the links on this backbone will be leased, a network planner at Acme has determined that a minimum spanning tree structure will be the most cost effective way to create the backbone to connect the 11 sites. This structure will ensure that all of the sites are connected to the backbone at the minimum cost of connection. The network planner has researched the costs (in dollars) to lease lines between the various sites per month which are listed in the following table:

 Chicago Dallas Detroit Los Angeles Miami New Orleans New York Pittsburgh San Francisco Seattle Tampa Chicago X 3000 1200 4800 1900 1500 900 700 4500 4200 1800 Dallas 3000 X 3200 2800 2200 1300 2600 2400 1300 2300 1400 Detroit 1200 3200 X 2200 3100 3300 1000 700 4100 4400 2000 Los Angeles 4800 2800 2200 X 3700 2700 5200 4700 300 1400 4100 Miami 1900 2200 3100 3700 X 1500 2400 2500 4400 4800 200 New Orleans 1500 1300 3300 2700 1500 X 2300 2900 4700 4800 2100 New York 900 2600 1000 5200 2400 2300 X 400 4500 4800 2200 Pittsburgh 700 2400 700 4700 2500 2900 400 X 4900 4500 1700 San Francisco 4500 1300 4100 300 4400 4700 4500 4900 X 500 3700 Seattle 4200 2300 4400 1400 4800 4800 4800 4500 500 X 3900 Tampa 1800 1400 2000 4100 200 2100 2200 1700 3700 3900 X

## Part 1. Computation tools

Given network above, create a spreadsheet to compute the cost of a set of connections.

You should use a spreadsheet to do this, such as XL 4 or Dismal.

## Part 2.

Use a minimum spanning tree algorithm to solve for the minimum cost wide area network backbone topology for Acme.

If this is computationally intractable for you, give a good answer and defend how it is good.