![](images/graphics/blank.gif)
Báo cáo toán học: "On the functions with values in [α(G), χ(G)]"
73
lượt xem 4
download
lượt xem 4
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
Let G be a graph with vertex set V (G) = {1, . . . , n} and edge set E(G). We are interested in studying the functions of the graph G whose values belong to the interval [(G), (G)]. Here (G) is the size of the largest stable set in G and (G) is the smallest number of cliques that cover the vertices of G. It is well known (see, for example, [1]) that for some 0 it is impossible to approximate in polynomial time (G) and (G) within a factor of n, assuming P 6= NP. We suppose that better approximation could...
Chủ đề:
Bình luận(0) Đăng nhập để gửi bình luận!
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD