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.
Fulltext:
PDF file (355 kB)