Independent sets with domination constraints (Q1962033)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent sets with domination constraints |
scientific article |
Statements
Independent sets with domination constraints (English)
0 references
20 March 2000
0 references
If \(\rho\) is a set of positive integers, then the \(\rho\)-IS problem is the problem to decide for a given graph \(G\), whether \(G\) has an independent set of vertices \(S\neq\varnothing\) with \(|S|\geq\min\{k\mid k\not\in\rho\}\) such that \(|N(v)\cap S|\in\rho\) for each \(v\in S\); here \(N(v)\) denotes the set of vertices adjacent to \(v\) in \(G\). Various cases of the \(\rho\)-IS problem are investigated from the viewpoint of algorithmic complexity.
0 references
domination
0 references
IS problem
0 references
independent set
0 references
algorithmic complexity
0 references