Earticle

초록

영어

Minimum vertex cover is very important among the NP-optimization problems and got the attention of the researchers in the past decade. Approximation techniques are used to solve the NP problems to get either optimal or near optimal solutions in polynomial time. In this paper, a modified vertex support algorithm is proposed that make use of same data structure as that of VSA but with different vertex selection criteria. Proposed algorithm is called advance vertex support algorithm (AVSA), it takes into account all the neighbors of a vertex twice while selection as surrounding vertices are very important for the decision. AVSA is analyzed experimentally against all benchmarks and compared with some better algorithms already present. The experimental results show that the worst approximation ratio was 1.032 with a ratio of average approximation 1.006. A comparative analysis with other algorithms indicates that AVSA can provide the best solution among them the minimum time requirements. Simplicity in design can give advantages to implement in various fields of application with minimum overhead.

목차

Abstract
 1. Introduction
 2. Literature review
 3. Proposed algorithm
  3.1. Empirical results
 4. Conclusion
 Acknowledgements
 References

키워드

저자

• Imran khan [ Department of Computer and Software Technology, University of Swat, KPK, Pakistan ]
• Israr Ahmad [ Department of Computer and Software Technology, University of Swat, KPK, Pakistan ]
• Muzammil Khan [ Department of Computer and Software Technology, University of Swat, KPK, Pakistan ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Advanced Science and Technology

• 간기

  월간

• pISSN

  2005-4238

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605