Advertisement
Published in:
01-02-2022
Complexity of the max cut Problem with the Minimal Domination Constraint
Published in: Journal of Applied and Industrial Mathematics | Issue 1/2022
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \(
G=(V,E,w)
\) be a simple weighted undirected graph with nonnegative edge weights. Let
\(
D
\) be a minimal dominating set in \(
G
\). The cutset induced by \(
D
\) is the set of edges with one vertex in the set \(
D
\) and the other in \(
V\setminus D
\). The weight of the cutset is the total weight of all its edges. The paper deals
with the problem of finding a cutset with the maximum weight among all minimal dominating
sets. In particular, the nonexistence of a polynomial approximation algorithm with a ratio better
than \(
|V|^{-\frac {1}{2}}
\) in the case of \(
\text {P}\ne \text {NP}
\) is proved.