- Tytuł:
- A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)
- Autorzy:
-
Khan, I.
Riaz, N. - Powiązania:
- https://bibliotekanauki.pl/articles/406436.pdf
- Data publikacji:
- 2015
- Wydawca:
- Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
- Tematy:
-
non-deterministic polynomial
vertex cover
independent set
benchmark
error ratio - Opis:
- The importance of non-deterministic polynomial (NP) problems in real world scenarios has compelled researchers to consider simple ways of finding approximate solutions to these problems in polynomial time. Minimum vertex cover is an NP complete problem, where the objective is to cover all the edges in a graph with the minimal number of vertices possible. The maximal independent set and maximal clique problems also belong to the same class. An important property that we have analyzed while considering various approaches to find approximate solutions to the minimum vertex cover problem (MVC) is that solving MVC directly can result in a bigger error ratio. We propose a new approximation algorithm for the minimum vertex cover problem called vertex cover using a maximum independent set (VCUMI). This algorithm works by removing the nodes of a maximum independent set until the graph is an approximate solution of MVC. Based on empirical results, it can be stated that VCUMI outperforms all competing algorithms presented in the literature. Based on all the benchmarks used, VCUMI achieved the worst case error ratio of 1.033, while VSA, MDG and NOVAC-1 gave the worst error ratios of 1.583, 1.107 and 1.04, respectively.
- Źródło:
-
Operations Research and Decisions; 2015, 25, 4; 5-18
2081-8858
2391-6060 - Pojawia się w:
- Operations Research and Decisions
- Dostawca treści:
- Biblioteka Nauki
Artykuł