Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia8592Heuristic Approach to the Problem ofMinimal Extension of a Communication Network and Its AssessmentBased on a Specialized Class of Weighted DigraphsGordonovAКафедра вычислительной техники; Колледж Стейтен Айленда, Нью-Йоркский городской университет; College of Staten Island, City University of New York-PetingiL; College of Staten Island, City University of New York-College of Staten Island, City University of New York150420084616708092016Copyright © 2008,2008In 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.networksGenetic AlgorithmNP-harddelay and cost constraints