Designing telecommunications networks using genetic algorithms and probabilistic minimum spanning trees

Faris N. Abuali, Dale A. Schoenefeld, Roger L. Wainwright

1994 · 35 citations · 11 references

DOIFull text

Open access

Concepts

Abstract

In this paper we investigate genetic algorithms (GA) as a .heuristic technique for obtaining near optimal solutions to the probabilistic minimum spanning tree (PMST) problem. The PMST problem is a natural generalization of the classical minimum spanning tree (MST) problem and is frequently a more realistic model. The PMST problem addresses the circumstances that arise when not all nodes are deterministically present but, rather, nodes are present with known probabilities. Although there are some special cases that are solvable in polynomial time, it is known that the PMST problem is NP-complete.

References

11