Discrete and Continuous Models and Applied Computational ScienceDiscrete 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)8592ArticlesСтатьиHeuristic Approach to the Problem ofMinimal Extension of a Communication Network and Its AssessmentBased on a Specialized Class of Weighted DigraphsЭвристический подход к проблеме минимального расширениякоммуникационной сети и его оценка, основанная на использовании специального класса графовGordonovAГордоновАКафедра вычислительной техники; Колледж Стейтен Айленда, Нью-Йоркский городской университет; 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 YorkКолледж Стейтен Айленда, Нью-Йоркский городской университетCollege of Staten Island, City University of New York150420084NO4 (2008)№4 (2008)616708092016Copyright ©; 2008, Гордонов А., Петинжи Л.2008Гордонов А., Петинжи Л.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/miph/article/view/8592In 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. В статье представлен эвристический подход к проблеме изменения топологии сети путём минимального расширения ориентированного графа G' с помощью добавления рёбер из суперграфа G графа G' таким образом, что сумма стоимостей новых рёбер минимальна и общая задержка между двумя выделенными узлами s и t удовлетворяет заранее определённым ограничениям. Для решения этой проблемы авторами разработан алгоритм генетического типа. Более того, проведена оценка эвристического подхода с использованием специального класса ориентированных графов, и показано, что решение проблемы минимального расширения коммуникационной сети с ограничениями на задержку принадлежит к классу NP-полных вычислительных задач. networksGenetic AlgorithmNP-harddelay and cost constraints1.Handler G. Y., Zang I. A Dual Algorithm for the Constrained Shortest Path Problem // Networks. - Vol. 10. - 1980. - Pp. 293-310.2.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.3.Sigurd M., Zachariasen M. Constrained Shortest Path // Proceeding of Algorithms-ESA 2004, 12-th Annual European Symposium. - Bergen, Norway: 2004. - P. 802.4.Eppstein D. Finding the -Shortest Paths // SIAM J. Computing. - Vol. 28(2). - 1998. - Pp. 652-673.5.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.6.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.