International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

Modified Vertex Support Algorithm: A New approach for approximation of Minimum vertex cover

    ,

Author Affiliations

  • 1University of Swat, PAKISTAN
  • 2SZABIST, Islamabad, PAKISTAN

Res. J. Computer & IT Sci., Volume 1, Issue (6), Pages 7-11, November,20 (2013)

Abstract

Graph related problems mostly belong to NP class and minimum vertex cover is one of them. Minimum vertex cover is focus point for researchers since last decade due to its vast areas of application. In this research paper we have presented a modified form of approximation algorithm for minimum vertex cover which makes use of data structure proposed already named vertex support. We changed the way of selection slightly from vertex support algorithm, vertices attached to minimum support node play very critical role in selection of vertices for minimum vertex cover and we used this in our algorithm. Using our approach we managed to reduce worst case approximation ratio of VSA which is 1.583 to 1.064, this is very major change in providing results with simplicity. Results are also compared with MDG and NOVAC in order to demonstrate the efficiency of selecting vertices in this manner. Simplicity in design can help in applying it in time restricted environments.

References

  1. 1. Chen J. et al,, Linear FPT reductions and computationallower bound,, Proc. 36th ACM symposium on Theory ofcomputing, New York, 212-221, (2004)
  2. 2. Garey M. and Johnson D.,, Computers and intractability,, New York: Freeman, (1979)
  3. 3. Karp R.,, Reducibility among combinatorial problems,, NewYork: Plenum Press, (1972)
  4. 4. Demaine E. et al,, Sub exponential parameterizedalgorithms on bounded-genus graphs and H-minor-freegraphs,, Journal of the ACM (JACM), 52(6), 866-893,(2005).
  5. 5. Dinur I and Safra S.,, on the hardness of approximatingminimum vertex cover, Annals of Mathematics,, (162),439-485 (2005)
  6. 6. Li S., et al,, An Approximation Algorithm for MinimumVertex Cover on General Graphs,, in Proc. 3rdInternational Symposium: Electronic Commerce andSecurity Workshops (ISECS ’10), China: Academy, 249-252, (2010)
  7. 7. Chvatal V.,, A Greedy Heuristic for the Set-CoveringProblem,, Mathematics of Operations Research, (4), 233-235, (1979)
  8. 8. Clarkson K.,, A modification to the greedy algorithm forvertex cover problem,, IPL, (16), 23-25, (1983)
  9. 9. Delbot F. and Laforest C.,, Analytical and experimentalcomparison of six algorithms for the vertex cover problem,, ACMJ. Experimental Algorithmics, (15), 1-4 (2010)
  10. 10. Chvatal V.,, A Greedy Heuristic for the Set-CoveringProblem,, Mathematics of Operations Research, (4), 233-235, (1979)
  11. 11. Cormen T.H., Lieserson C.E, Rivest R.L. and Stein C.,, Introduction to Algorithms, 3rd Ed,, MIT Press England,(2009)
  12. 12. Halldorsson M. and Radhakrishnan J.,, Greed is good:Approximating independent sets in sparse and boundeddegreegraphs,, In Proc. 26th Annual ACM Symposium onTheory of Computing, New York: ACM,439–448, (1994)
  13. 13. Avis D. and Imamura T.,, A List Heuristic for VertexCover,, Operations research letters, 35(2), 201-204, (2007)
  14. 14. Delbot F. and Laforest C.,, A better list heuristic for vertexcover,, Information Processing Letters, (107), 125-127,(2008)
  15. 15. Balaji S., Swaminathan V. and Kannan K.,, Optimization ofUn-weighted Minimum Vertex Cover,, World Academy ofScience, Engineering and technology, (67), 508-513(2010)
  16. 16. Gajurel S. and Bielefeld R.,, A Simple NOVCA: NearOptimal Vertex Cover Algorithm,, Procedia ComputerScience, (9), 747-753 (2012)