Independent sets with domination constraints
From MaRDI portal
Publication:1962033
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.
Recommendations
Cites work
- Approximating maximum independent sets by excluding subgraphs
- Approximating the minimum maximal independence number
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 617552 (Why is no real title available?)
- scientific article; zbMATH DE number 1559517 (Why is no real title available?)
- scientific article; zbMATH DE number 794265 (Why is no real title available?)
- The complexity of satisfiability problems
Cited in
(27)- A constrained independent set problem for matroids
- Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets
- Structurally parameterized \(d\)-scattered set
- An overview of \((\kappa, \tau)\)-regular sets and their applications
- Competitive router scheduling with structured data
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- An approximation result for matchings in partitioned hypergraphs
- Truthfulness and approximation with value-maximizing bidders
- Relations between ( , )-regular sets and star complements.
- Shrinking maxima, decreasing costs: new online packing and covering problems
- On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
- scientific article; zbMATH DE number 1223713 (Why is no real title available?)
- A Taxonomy of Perfect Domination
- Overflow management with self-eliminations
- Overflow management with self-eliminations
- On the parameterized complexity of compact set packing
- Improved (In-)Approximability Bounds for d-Scattered Set
- A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
- Branch and recharge: exact algorithms for generalized domination
- On the parameterized complexity of compact set packing
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
- Parameterized complexity of modular dominating structures in bounded-treewidth graphs
- Residue domination in bounded-treewidth graphs
- Spectral results on graphs with regularity constraints
- Spectral results on regular graphs with (k,)-regular sets
- Main eigenvalues and \((\kappa ,\tau )\)-regular sets
- Integral graphs and \((k,\tau )\)-regular sets
This page was built for publication: Independent sets with domination constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962033)
