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
    0 references
    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

    Identifiers