solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看192次
Approximation algorithms on $k-$ cycle covering and $k-$ clique covering. (arXiv:1807.06867v1 [cs.DM])
来源于:arXiv
Given a weighted graph $G(V,E)$ with weight $\mathbf w: E\rightarrow
Z^{|E|}_{+}$. A $k-$cycle covering is an edge subset $A$ of $E$ such that $G-A$
has no $k-$cycle. The minimum weight of $k-$cycle covering is the weighted
covering number on $k-$cycle, denoted by $\tau_{k}(G_{w})$. In this paper, we
design a $k-1/2$ approximation algorithm for the weighted covering number on
$k-$cycle when $k$ is odd.
Given a weighted graph $G(V,E)$ with weight $\mathbf w: E\rightarrow
Z^{|E|}_{+}$. A $k-$clique covering is an edge subset $A$ of $E$ such that
$G-A$ has no $k-$clique. The minimum weight of $k-$clique covering is the
weighted covering number on $k-$clique, denoted by
$\widetilde{\tau_{k}}(G_{w})$. In this paper, we design a $(k^{2}-k-1)/2$
approximation algorithm for the weighted covering number on $k-$clique. Last,
we discuss the relationship between $k-$clique covering and $k-$clique packing
in complete graph $K_{n}$. 查看全文>>