Heuristic Approach to the Problem ofMinimal Extension of a Communication Network and Its AssessmentBased on a Specialized Class of Weighted Digraphs

In the paper we are presenting a heuristic approach to solve the problem of changing network topology by minimally extending a digraph G′ through adding edges from a given spanning supergraph G of G', such that the sum of the costs of the new edges is minimum, and in the new graph the end-to-end delay between two distinguished vertices s and t meets a predefined time constraint (ME problem). We develop a heuristic based upon the Genetictype algorithm technique. Moreover, the application of this heuristic is justified and is shown that the solution of ME problem belongs to the NP-hard computational class.

networks, Genetic Algorithm, NP-hard, delay and cost constraints