Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:4, 792-801
Volume 27, No 4, 2020, P. 5-20
UDC 519.8+518.25
V. V. Voroshilov
A maximum dicut in a digraph induced by a minimal dominating set
Abstract:
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\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 {$S \to \overline{S}$} is a set of edges ($i, j$) $\in A$ such that $i \in S$ and $j \in$ V\S. The weight of a dicut is the total weight of all its edges. The article deals with the problem of finding a dicut {$S \to \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.
DOI: 10.33048/daio.2020.27.691
Vladimir V. Voroshilov 1
1. Dostoevsky Omsk State University,
55a Mir Avenue, 644077 Omsk, Russia
e-mail: voroshil@gmail.com
Received May 27, 2020
Revised June 19, 2020
Accepted June 22, 2020
References
[1] N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, London, 1975; Mir, Moscow, 1978 [Russian]).[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), pp. 85–103.
[3] A. Ageev, R. Hassin, and M. Sviridenko, A 0.5-approximation algorithm for max dicut with given sizes of parts, SIAM J. Discrete Math. 14 (2), 246–255 (2001).
[4] J. Lee, N. Viswanath, and X. Shen, Max-cut under graph constraints, Programming and Combinatorial Optimization (Proc. 18th Int. Conf., Liège, Belgium, June 1–3, 2016) (Springer, Cham, 2016), pp. 50–62 (Lect. Notes Comput. Sci., Vol. 9682).
[5] G. A. Cheston, G. Fricke, S. T. Hedetniemi, and D. P. Jacobs, On the computational complexity of upper fractional domination, Discrete Appl. Math. 27 (3), 195–207 (1990).
[6] N. Boria, F. Della Croce, and V. Th. Paschosdef, On the max min vertex cover problem, Discrete Appl. Math. 196, 62–71 (2015).
[7] R. Yu. Simanchev, I. V. Urazova, V. V. Voroshilov, V. V. Karpov, and 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), 170–179 (2019) [Russian].
[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
