- Tytuł:
- An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
- Autorzy:
-
Tu, Jianhua
Shi, Yongtang - Powiązania:
- https://bibliotekanauki.pl/articles/31343724.pdf
- Data publikacji:
- 2019-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
combinatorial optimization
vertex cover P3 problem
branch- width
planar graphs
EPTAS - Opis:
- Given a graph G = (V,E), the task in the vertex cover P3(VCP3) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP3 problem on planar graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 55-65
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł