We present a study of two NP-hard telecommunications network design problems – the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division multiplexing. The first problem, the PCGMST problem, involves the design of regional backbone networks, where a set of local area networks (LANs) need to be connected by a minimum cost tree network using exactly one gateway site from each LAN. We present several polynomial time heuristics for the PCGMST problem and show that these algorithms, at best, provide only modest quality solutions…
Author: Stanojevic, Daliborka
Source: University of Maryland
Download Link: Click Here To Download This Report (PDF)
Reference URL 1: Visit Now
Reference URL 2: Visit Now