Евристичний підхід до вирішення задачі про найменше покриття з використанням гарантованого прогнозування

Автор(и)

  • S V LISTROVOY Ukrainian State University of Railway Transport, Україна
  • S V MOTSNYI Ukrainian State University of Railway Transport,

DOI:

https://doi.org/10.18664/ikszt.v0i3.53232

Ключові слова:

guaranteed predictions, nonlinear equations, leaf vertices

Анотація

У даній статті описується евристичний підхід до вирішення задачі про найменше покриття з використанням гарантованого прогнозування. Завдяки високому ступеню розпаралелювання операцій з'являється можливість його ефективної реалізації в системах з великою кількістю обчислювальних ядер. Була написана програма на мові програмування C++ для проведення експериментального дослідження. Згідно з результатами, даний підхід найбільш оптимізований для графів з високою щільністю.

Біографії авторів

S V LISTROVOY, Ukrainian State University of Railway Transport

Doctor of Technical Sciences, Full Professor

S V MOTSNYI, Ukrainian State University of Railway Transport

graduate student

Посилання

Richard M. Karp. Reducibility among combinatorial problems (In Complexity of computer computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103, Plenum, 1972.

Burkhard Monien and Ewald Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform., 22(1):115–123, 1985.

Yong Zhang, Qi Ge, Rudolf Fleisher, Tao Jiang, and Hong Zhu. Approximating the minimum weight weak vertex cover. Theoretical Computer Science, 363(1):99–105, 2006.5. - Volume 7, Issue 4 (Nov., 1992), 404-416.

Chantal Roth-Korostensky. Algorithms for building multiple sequence alignments and evolutionary trees. Doctoral thesis, ETH Zurich, Institute of Scientific Computing, 2000.

Ulrike Stege. Resolving conflicts in problems from computational biology. Doctoral thesis, ETH Zurich, Institute of Scientific Computing, 2000.

Michael R. Fellows. Parameterized complexity: the main ideas and some research frontiers. In Algorithms and computation (Christchurch, Lecture Notes), pages 291–307. Springer, Berlin, 2001.

Jianer Chen, Iyad A. Kanj, and Ge Xia. Simplicity is beauty: Improved upper bounds for vertex coverTechnical Report 05-008, Texas A&M University, Utrecht, the Netherlands, April 2005.

George Karakostas. A better approximation ratio for the vertex cover problem. In ICALP 2005, volume 3580 of LNCS, pages 1043–1050, Lisboa, Portugal, June 2005. Springer-Verlag Berlin Heidelberg.

##submission.downloads##

Опубліковано

2015-07-02

Номер

№ 3 (2015): Інформаційно-керуючі системи на залізничному транспорті

Розділ

Статті

Ліцензія

Авторське право (c) 2015 S V LISTROVOY, S V MOTSNYI

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.