TY - JOUR
T1 - Approximation for vertex cover in β -conflict graphs
AU - Miao, Dongjing
AU - Cai, Zhipeng
AU - Tong, Weitian
AU - Li, Jianzhong
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media New York.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - Conflict graph is a union of finite given sets of disjoint complete multipartite graphs. Vertex cover on this kind of graph is used first to model data inconsistency problems in database application. It is NP-complete if the number of given sets r is fixed, and can be approximated within 2-12r (Miao et al. in Proceedings of the 9th international conference on combinatorial optimization and applications, vol 9486. COCOA 2015, New York. Springer, New York, pp 395–408, 2015). This paper shows a better algorithm to improve the approximation for dense cases. If the ratio of vertex not belongs to any wheel complete multipartite graph is no more than β< 1 , then our algorithm will provide a (1+β+1-βk)-approximation, where k is a parameter related to degree distribution of wheel complete multipartite graph.
AB - Conflict graph is a union of finite given sets of disjoint complete multipartite graphs. Vertex cover on this kind of graph is used first to model data inconsistency problems in database application. It is NP-complete if the number of given sets r is fixed, and can be approximated within 2-12r (Miao et al. in Proceedings of the 9th international conference on combinatorial optimization and applications, vol 9486. COCOA 2015, New York. Springer, New York, pp 395–408, 2015). This paper shows a better algorithm to improve the approximation for dense cases. If the ratio of vertex not belongs to any wheel complete multipartite graph is no more than β< 1 , then our algorithm will provide a (1+β+1-βk)-approximation, where k is a parameter related to degree distribution of wheel complete multipartite graph.
KW - Approximation algorithm
KW - Complete multipartite graph
KW - Conflict graph
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=85015759061&partnerID=8YFLogxK
U2 - 10.1007/s10878-017-0127-z
DO - 10.1007/s10878-017-0127-z
M3 - Article
AN - SCOPUS:85015759061
SN - 1382-6905
VL - 34
SP - 1052
EP - 1059
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 4
ER -