Listrovoy Sergey Vladimirovich; Motsnyi Stanislav Vladimirovich

The Probabilistic Method for Solving Minimum Vertex Cover Problem Using Systems of Nonlinear Equations

Full Text (PDF, 362KB), PP.1-8

Views: 0 Downloads: 0

Author(s)

Listrovoy Sergey Vladimirovich ^1,* Motsnyi Stanislav Vladimirovich ¹

1. Ukrainian State University of Railway Transport, Dept. of Specialized Computer Systems, Kharkiv, 61050, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2015.11.01

Received: 23 Feb. 2015 / Revised: 21 Jun. 2015 / Accepted: 2 Aug. 2015 / Published: 8 Oct. 2015

Index Terms

Vertex Covers, Undirected Graphs, Leaf Vertices, Approximation Algorithm

Abstract

In this paper the probabilistic method is presented for solving the minimum vertex cover problem using systems of non-linear equations that are formed on the basis of a neighborhood relationship of a particular vertex of a given graph. The minimum vertex cover problem is one of the classic mathematical optimization problems that have been shown to be NP-hard. It has a lot of real-world applications in different fields of science and technology. This study finds solutions to this problem by means of the two basic procedures. In the first procedure three probabilistic pairs of variables according to the maximum vertex degree are formed and processed accordingly. The second procedure checks a given graph for the presence of the leaf vertices. Special software package to check the validity of these procedures was written. The experiment results show that our method has significantly better time complexity and much smaller frequency of the approximation errors in comparison with one of the most currently efficient algorithms.

Cite This Paper

Listrovoy Sergey Vladimirovich, Motsnyi Stanislav Vladimirovich, "The Probabilistic Method for Solving Minimum Vertex Cover Problem Using Systems of Non-linear Equations", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.11, pp.1-8, 2015. DOI:10.5815/ijitcs.2015.11.01

Reference

[1]Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, 1 edition (April 20, 2009), New York: Cambridge University Press, pp. 38-44.

[2]M. Garey and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.

[3]Yong Zhang, Qi Ge, Rudolf Fleisher, Tao Jiang, and Hong Zhu, “Approximating the minimum weight weak vertex cover,” in Theoretical Computer Science, vol. 363(1), Amsterdam: Elsevier, 2006, pp. 99-105.

[4]Paul Erdös, “Graph theory and probability,“ in Can. J. Math, vol. 11, Ottawa: Canadian Mathematical Society, 1959, pp. 34-38.

[5]Yaser Khamayseseh, Wail Mardini, Anas Shantnawi, “An Approximation Algorithm for Vertex Cover Problem,” International Conference on Computer Networks and communication Systems (CNCS 2012) IPCSIT, vol.35, Singapore: IACSIT Press, 2012, pp. 69-72.

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

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

[8]Sangeeta Bansal and Ajay Rana, “Analysis of Various Algorithms to Solve Vertex Cover Problem,” in IJITEE, vol. 3, issue 12, Bhopal: BEIESP, May 2004, pp. 4-6.

[9]Vijay V. Vazirani, Approximation Algorithms, Berlin: Springer Verlag, Corrected Second Printing, 2003.

[10]Christos H Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, New York: Dovel Publications Inc., 1998.

[11]D. Hochbaum, “Efficient bounds for the stable set, vertex cover and set packing problems,“ in Discrete Applied Mathematics, vol. 6, Elsevier: University of California, 1983, pp. 243-254.

[12]George Karakostas, “A Better Approximation Ratio for the Vertex Cover Problem,” in Automata, Languages and Programming, vol. 3580, Lisbon: ICALP, 2005, pp. 1043-1050.

[13]Michael R. Fellows, “Parameterized complexity: the main ideas and some research frontiers,“ in Algorithms and computation (Christchurch, Lecture Notes), vol. 2223, Berlin: Springer, 2001, pp. 291–307.

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

[15]Erdös Paul, Rényi Alfréd, “On the evolution of random graphs.” Bull. Inst. Int., No.4, 1961, pp. 343-347. [Reviewer: G.Mihoc], 05C80.

[16]S V Listrovoy, S V Minukhin and S V Znakhur, Investigation of the Scheduler for Heterogeneous Distributed Computing Systems based on Minimal Cover Method // International Journal of Computer Applications (0975 – 8887), Volume 51, No.19, August 2012, рp. 35-44, doi: 10.5120/ hfes.8154-1948.

[17]Albert-László Barabási, Eric Bonabeau, “Scale-Free Networks,” in Scientific American, vol. 288(5), May 2003, pp. 60-69.

International Journal of Information Technology and Computer Science (IJITCS)