A heuristic approach to solving the minimum vertex cover problem using guaranteed predictions

Автор(и)

  • 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

Анотація

This paper presents a heuristic approach to solving the minimum vertex cover problem with guaranteed predictions, which can be effectively implemented on the multi-core platforms because of the high degree of the instruction-level parallelism. The C++ program to compute and display the figures of the test results for each experiment was written.
According to the results this approach is optimized for the very dense graphs.

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

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.