Scientific and Technical Journal

ELECTROTECHNIC AND COMPUTER SYSTEMS

ISSN Print 2221-3937
ISSN Online 2221-3805
SOLVABLE PROBLEM AND СOMBINATORIAL OPTIMIZATION
Abstract:
А structure-alphabetical search method of decision of problems of сombinatorial optimization, based on recognition of a structure of input data and one solvable case, characterized by high speed and accuracy of finding the optimal result is described. It is also shown that some the unsolvableproblems of this class aretakento polynomial solvable or contain the subclass of solvable problems. 
Authors:
Keywords
DOI
10.15276/etks.13.89.2014.07
References

1. Papadimitriou Х. and Steiglitz K. Ком-binatornaja оptimizatsija. Аlgoritmy i slojnost [Combinatorial Optimization. Algorithms and Complexity], 1985, Mir Publ., Moscow, Russian Federation, 510 p. (In Russian).

2. Sergienko I. V., and Каspthitzkaja M. F. Modeli i metodu reshenija na EVM kombinatornux zadath optimizatzii [Models and Methods of Computer Solutions of Combinatorial Optimization Problems], (1981),Sciences Dumka Publ., Kiev, Ukraine, 281 p. (In Russian).

3. Tymofijeva N.K. Теоrетyкоtzyslovi метоdy rоzvjazannja zadath kombinatornoi optimizatzii [TheoreticalNumerical Methods Used to Solve Combinatorial Optimization Problems], (2007),Тне Thesis for Doctor’s Degree in Technical Sciences on Speciality 01.05.02 – Modelling and Numerical Methods Mathema-tical, Kyiv,Ukraine, V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, 32 p. (In Ukrainian).

4. Veen Jack A.A., Van Der, Sierksma Gerard, and Dal Rene Van. Pyramidal Tours and the Travelling Salesman Problem, (1991), Eur. J. Oper.  Res., Vol. 52, No. 1, pp. 90102.

5. Kalmancon K. Edgeconvex Circuits and the Traveling Salesman Problem, (1975),Canad. J. Math., Vol. 27, No. 5, pp. 10001010.

6. Supnick F. Extreme Нamiltonian Lines, (1957),Annals of Math., Vol. 66, pp. 179201.

7. Belov I.S. Alternirovannaja zadatha kommivojazhera [Alternating Traveling Salesman Problem] Extras. National Academy of Sciences of Ukraine, 2004, No. 8, pp. 1519 (In Russian).

8. Jeromin Bernd. Untersuchungen zu Eeiner Dualisierung des Rundreise problems, (1990), Wiss. Z. Techn. Univ., Drasden,Vol 39, No. 1, pp. 174182.

9. Timofeeva N.К. Matritsu v zadathax kombinatornoj optimizatzii [The Matrix in the Problems of the Combinatorial Optimization], Journal of Automation and Information Sciences Publ., 1996, No. 3, pp. 104113 (In Russian).

10. Tymofijeva N. К. Pro sposoby zveden-nja nerozvjaznyx zadath kombinatornoi optimi-zatzii do rozvjaznyx [About the Methods of Reduction of Insolvable Problem of Combinato-rial Optimization to Solvable Problem],Journal of Vinnitsa Polytechnic Institute Publ., Vinnitsa, Ukraine,2011, No. 3, pp. 240244(In Ukrainian).

11. Timofeeva N.К. Podklassu razre-tsimux zadath iz klassov zadath kombinatornoj optimizatzii [Subclasses of Solvable Problem from the Classes of Combinatorial Optimization], Kibernetika i Sistemny Analiz Publ., 2009, No. 2, pp. 97105 (In Russian).

Published:
Last download:
2017-11-16 11:49:09

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2014. Any use of information from the site is possible only under the condition that the source link! ]
Яндекс.Метрика