Complexity of majority monopoly and signed domination problems

DOI10.1016/j.jda.2011.12.019zbMath1237.68090MaRDI QIDQ414422

Sounaka Mishra

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

zbMATH Keywords

dominating set; approximation algorithms; signed domination

Mathematics Subject Classification ID

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

Approximability of open \(k\)-monopoly problems

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