Autor: Tu, Jianhua - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P₃ 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 P₃(VCP₃) 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 VCP₃ 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 VCP₃ 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 VCP₃ 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ł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
Autorzy:: Sun, Yuefang
Jin, Zemin
Tu, Jianhua
Powiązania:: https://bibliotekanauki.pl/articles/31342242.pdf
Data publikacji:: 2018-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: Rainbow total-coloring
rainbow total-connection number
complementary graph
Erdős-Gallai type problem
Opis:: A total-colored graph $G$ is rainbow total-connected if any two vertices of $G$ are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by $ rtc(G) $, of a graph $G$ is the minimum number of colors needed to make $G$ rainbow total-connected. In this paper, we prove that $ rtc(G) $ can be bounded by a constant 7 if the following three cases are excluded: $ diam( \overline{G} ) = 2 $, $ diam( \overline{G} ) = 3 $, $ \overline{G} $ contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function $ f(n, k) $, where $ f(n, k) $ is the minimum value satisfying the following property: if $ |E(G)| \ge f(n, k) $, then $ rtc(G) \le k $.
Źródło:: Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1023-1036
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "Tu, Jianhua" wg kryterium: Autor

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język