solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3363次
Approximating Connected Safe Sets in Weighted Trees. (arXiv:1711.11412v1 [math.CO])
来源于:arXiv
For a graph $G$ and a non-negative integral weight function $w$ on the vertex
set of $G$, a set $S$ of vertices of $G$ is $w$-safe if $w(C)\geq w(D)$ for
every component $C$ of the subgraph of $G$ induced by $S$ and every component
$D$ of the subgraph of $G$ induced by the complement of $S$ such that some
vertex in $C$ is adjacent to some vertex of $D$. The minimum weight $w(S)$ of a
$w$-safe set $S$ is the safe number $s(G,w)$ of the weighted graph $(G,w)$, and
the minimum weight of a $w$-safe set that induces a connected subgraph of $G$
is its connected safe number $cs(G,w)$. Bapat et al. showed that computing
$cs(G,w)$ is NP-hard even when $G$ is a star. For a given weighted tree
$(T,w)$, they described an efficient $2$-approximation algorithm for $cs(T,w)$
as well as an efficient $4$-approximation algorithm for $s(T,w)$. Addressing a
problem they posed, we present a PTAS for the connected safe number of a
weighted tree. Our PTAS partly relies on an exact pseudopolynomial time
algor 查看全文>>