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.