Abstract:
Let $G=(V,E,w)$ be a simple weighted undirected graph with nonnegative weights of its edges. Let $D$ be a minimal dominating set in $G.$ Cutset induced by $D$ is a set of edges with one vertex in the set $D$ and the other in $V\setminus D.$ The weight of a cutset is the total weight of all its edges. The paper deals with the problem of finding a cutset with maximum weight among all minimal dominating sets. In particular, nonexistence of polynomial approximation algorithm with ratio better than $|V|^{-\frac{1}{2}}$ in case of $\text{P}\ne\text{NP}$ is proved. Illustr. 3, bibliogr. 8.
Fulltext:
PDF file (299 kB)