Anzeige
Erschienen in:
01.11.2020
A Maximum Dicut in a Digraph Induced by a Minimal Dominating Set
Erschienen in: Journal of Applied and Industrial Mathematics | Ausgabe 4/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(\{S\rightarrow \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 \(\{S\rightarrow \overline {S}\}
\) with maximum weight among all minimal
dominating sets.