Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)8592Heuristic 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[Handler G. Y., Zang I. A Dual Algorithm for the Constrained Shortest Path Problem // Networks. - Vol. 10. - 1980. - Pp. 293-310.][Gellermann T., Sellmann M., Wright R. Shortest Path Constraints for the Resource Constrained Shortest Path Problem // Lecture Notes in Computer Science. - 2005. - Vol. 3524/2005. - Pp. 201-216.][Sigurd M., Zachariasen M. Constrained Shortest Path // Proceeding of Algorithms-ESA 2004, 12-th Annual European Symposium. - Bergen, Norway: 2004. - P. 802.][Eppstein D. Finding the -Shortest Paths // SIAM J. Computing. - Vol. 28(2). - 1998. - Pp. 652-673.][J. Hershberger M. M., Suri S. Finding the Shortest Simple Paths: A New Algorithm and its Implementation // Proceeding of the Fifth Workshop on Algorithm Engineering and Experiments. ALENEX 2003. - Baltimore, MD, USA: 2003. - Pp. 26-36.][Lawler E. L. A Procedure for Computing the Best Solutions to Discrete Optimization Problems and its Application to the Shortest Path Problem // Management Science. - Vol. 18. - 1972. - Pp. 401-405.]