Complexity of the max cut problem with~the~minimal domination constraint
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 5-17
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
graph, cutset, dominating set, weighted graph, optimization problem, approximation.
@article{DA_2022_29_1_a0,
author = {V. V. Voroshilov},
title = {Complexity of the max cut problem with~the~minimal domination constraint},
journal = {Diskretnyj analiz i issledovanie operacij},
pages = {5--17},
publisher = {mathdoc},
volume = {29},
number = {1},
year = {2022},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/}
}
V. V. Voroshilov. Complexity of the max cut problem with~the~minimal domination constraint. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 5-17. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/