|
This article is cited in 2 scientific papers (total in 2 papers)
A maximum dicut in a digraph induced by a minimal dominating set
V. V. Voroshilov Dostoevsky Omsk State University, 55a Mir Avenue, 644077 Omsk, Russia
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\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.
Received: 27.05.2020 Revised: 19.06.2020 Accepted: 22.06.2020
Citation:
V. V. Voroshilov, “A maximum dicut in a digraph induced by a minimal dominating set”, Diskretn. Anal. Issled. Oper., 27:4 (2020), 5–20; J. Appl. Industr. Math., 14:4 (2020), 792–801
Linking options:
https://www.mathnet.ru/eng/da1265 https://www.mathnet.ru/eng/da/v27/i4/p5
|
Statistics & downloads: |
Abstract page: | 179 | Full-text PDF : | 92 | References: | 22 |
|