Minimum Spanning Tree (Telecommunications) Homework Problem

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. Since 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

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