Complexity of majority monopoly and signed domination problems
From MaRDI portal
Publication:414422
DOI10.1016/j.jda.2011.12.019zbMath1237.68090MaRDI QIDQ414422
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.019
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Efficient bounds for the stable set, vertex cover and set packing problems
- Optimization, approximation, and complexity classes
- Signed domination in regular graphs and set-systems
- On the signed domination in graphs
- Inequalities relating domination parameters in cubic graphs
- Signed domination in regular graphs
- Majority domination in graphs
- Complexity of approximating bounded variants of optimization problems
- A threshold of ln n for approximating set cover
- Domination in graphs with minimum degree two
- A Greedy Heuristic for the Set-Covering Problem
- Non-approximability results for optimization problems on bounded degree instances
- STACS 2005