Geodesic
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/}
}
TY  - JOUR
AU  - V. V. Voroshilov
TI  - Complexity of the max cut problem with~the~minimal domination constraint
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 5
EP  - 17
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/
LA  - ru
ID  - DA_2022_29_1_a0
ER  - 
%0 Journal Article
%A V. V. Voroshilov
%T Complexity of the max cut problem with~the~minimal domination constraint
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 5-17
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/
%G ru
%F 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/