Power estimation of the full set of alternatives to Paret's subgraphs in a graph
https://doi.org/10.20914/2310-1202-2018-2-73-76
Abstract
In practice problems of creation of an optimum subgraph of a certain look in a given graph count often meet. As possible annexes problems of search of optimum structure of technological networks, design of architecture of computers, modeling of artificial intelligence and many others are used. More and more relevant are multicriteria options of the specified tasks. An essential limiting factor of improvement of methods of multicriteria optimization on graphs is the problem of their exponential computing complexity caused by big dimension of a task. A number of data demonstrates that the theoretical assessment of complexity constructed for methods of full search isn't true, and the drawn conclusions have no sufficient justification. Among effective decisions the so-called complete set of alternatives which power can be lower on orders, than the power of the Pareto set is of the greatest interest. Taking into account the listed facts in this work the result of researches consisting in creation of assessment from above for the power of a complete set of alternatives of a problem of stay is stated pareto-optimal subgraphs for a given graph.
About the Authors
Yu. V. Bugaev
Voronezh state university of engineering technologies
Russian Federation
Dr. Sci. (Phys.-Math.), professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
Russian Federation
Dr. Sci. (Phys.-Math.), professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
S. V. Chikunov
Voronezh state university of engineering technologies
Cand. Sci. (Engin.), associate professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
Cand. Sci. (Engin.), associate professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia
References
1. Melkumov V.N., Kuznetsov I.S., Kobelev V.N. The problem of finding the optimal structure of heat networks. Nauchnyi vestnik VGASU [Scientific Bulletin of the Voronezh state University of architecture and construction. Construction and architecture] 2011. no. 2. pp. 37-42. (in Russian)
2. Ilyasova N. Yu,. Korepanov A.O., Chikulaev P.M. Method of selection of Central lines of blood vessels on diagnostic images. Komp’yuternaya optika [Computer optics] 2006. no. 29. pp. 146-150. (in Russian)
3. Popov A. Yu. On the implementation of the algorithm of Ford-Fulkerson in a computing system, with many streams of commands and a single data stream. Nauka I obrazovanie [Science and education] 2014. no. 9. pp. 162-180. (in Russian)
4. Williams J., Massie Ch., George A.D., Richardson J. et al. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration. ACM Transactions onReconfigurable Technology and Systems. 2010. vol. 3, no. 4. art.no. 19.
5. Nguyen Q.H., Ong Y.S., Krasnogor N.A. Study on the Design Issues of Memetic Algorithm. IEEE Congress on Evolutionary Computation (CEC 2007). 2007. pp. 2390–2397.
6. Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics. 2006. vol. 36. no. 1. pp. 141–152.
7. Jie J., Zeng J. Improved Mind Evolutionary Computation for Optimizations. Proceedings of 5 th World Congress on Intelligent Control and Automation. 2004. vol. 3. pp. 2200–2204.
8. Liang J.J., Qu B.Y., Suganthan P.N. Problem Definitions and Evaluation Criteria for the CEC 2014 Special Session and Competition on Single Objective Real-Parameter Numerical Optimization. Technical Report 201311. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China; Technical Report. Singapore: NanyangTechnologicalUniversity, 2013. 32 p.
9. Bugaeev Yu.V., Muzalevsky F.A. Polynomial estimation of power of the set of Paret paths in the graph. Vestnik Nizhegorodskogo universiteta [Proceedings of Nizhny Novgorod University] 2013. no. 2-1. pp. 168-170. (in Russian)
10. Kostyukova N.I. Graphs and their application. Kombinatornue algoritmy dlya programistov [Combinatorial algorithms for programmers: Studies. benefit] Moscow, BINOM, 2010. 311 p. (in Russian)
Review
For citations:
Bugaev Yu.V., Chikunov S.V. Power estimation of the full set of alternatives to Paret's subgraphs in a graph. Proceedings of the Voronezh State University of Engineering Technologies. 2018;80(2):73-76. (In Russ.) https://doi.org/10.20914/2310-1202-2018-2-73-76
Views:
559
Email this article 
Post a Comment 
