Geodesic
A maximum dicut in a digraph induced by a minimal dominating set
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 5-20 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $G = (V,A)$ be a simple directed graph and let $S\subseteq V$ be a subset of the vertex set $V$. The set $S$ is called dominating if for each vertex $j\in V\setminus S$ there exist at least one $i\in S$ and an edge from $i$ to $j$. A dominating set is called (inclusion) minimal if it contains no smaller dominating set. A dicut $\overline{S}$ is a set of edges $(i,j)\in A$ such that $i\in S$ and $j\in V\setminus S$. The weight of a dicut is the total weight of all its edges. The article deals with the problem of finding a dicut $\overline{S}$ with maximum weight among all minimal dominating sets. Illustr. 6, bibliogr. 8.
Keywords: directed graph, weighted graph, maximum dicut, inclusion minimal dominating set. 
@article{DA_2020_27_4_a0,
     author = {V. V. Voroshilov},
     title = {A~maximum dicut in~a~digraph induced by~a~minimal~dominating~set},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--20},
     year = {2020},
     volume = {27},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_4_a0/}
}
TY  - JOUR
AU  - V. V. Voroshilov
TI  - A maximum dicut in a digraph induced by a minimal dominating set
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 5
EP  - 20
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_4_a0/
LA  - ru
ID  - DA_2020_27_4_a0
ER  - 
%0 Journal Article
%A V. V. Voroshilov
%T A maximum dicut in a digraph induced by a minimal dominating set
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 5-20
%V 27
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2020_27_4_a0/
%G ru
%F DA_2020_27_4_a0
V. V. Voroshilov. A maximum dicut in a digraph induced by a minimal dominating set. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 5-20. http://geodesic.mathdoc.fr/item/DA_2020_27_4_a0/

[1] N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, London, 1975 | MR

[2] R. M. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Computations, Proc. Symp. CCC (Yorktown Heights, USA, March 20–22, 1972), Plenum Press, New York, 1972, 85–103 | DOI | MR

[3] A. Ageev, R. Hassin, M. Sviridenko, “A 0.5-approximation algorithm for max dicut with given sizes of parts”, SIAM J. Discrete Math., 14:2 (2001), 246–255 | DOI | MR | Zbl

[4] J. Lee, N. Viswanath, X. Shen, “Max-cut under graph constraints”, Programming and Combinatorial Optimization, Proc. 18th Int. Conf. (Liège, Belgium, June 1-3, 2016), Lect. Notes Comput. Sci., 9682, Springer, Cham, 2016, 50–62 | DOI | MR | Zbl

[5] G. A. Cheston, G. Fricke, S. T. Hedetniemi, D. P. Jacobs, “On the computational complexity of upper fractional domination”, Discrete Appl. Math., 27:3 (1990), 195–207 | DOI | MR | Zbl

[6] N. Boria, F. Della Croce, V. Th. Paschosdef, “On the max min vertex cover problem”, Discrete Appl. Math., 196 (2015), 62–71 | DOI | MR | Zbl

[7] R. Yu. Simanchev, I. V. Urazova, V. V. Voroshilov, V. V. Karpov, A. A. Korableva, “Selection of the key-indicator system for the economic security of a region using a (0, 1)-programming model”, Vestn. Omsk. Univ., Ser. Ekonomika, 17:3 (2019), 170–179 (Russian) | MR

[8] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl