Complexity of majority monopoly and signed domination problems

DOI10.1016/J.JDA.2011.12.019MaRDI QIDQ414422zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsdominating setsigned domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 1954391
• Approximability of open \(k\)-monopoly problems
• Minimum monopoly in regular and tree graphs
• Max- and Min-neighborhood monopolies
• Algorithms and Hardness for Signed Domination

Cites work

• scientific article; zbMATH DE number 1124597 (Why is no real title available?)
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• scientific article; zbMATH DE number 825134 (Why is no real title available?)
• scientific article; zbMATH DE number 861417 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Approximation algorithms for NP-hard problems.
• Complexity of approximating bounded variants of optimization problems
• Domination in graphs with minimum degree two
• Efficient bounds for the stable set, vertex cover and set packing problems
• Improved performance of the greedy algorithm for partial cover
• Inequalities relating domination parameters in cubic graphs
• Majority domination in graphs
• Non-approximability results for optimization problems on bounded degree instances
• On the signed domination in graphs
• Optimization, approximation, and complexity classes
• STACS 2005
• Signed domination in regular graphs
• Signed domination in regular graphs and set-systems

Cited in

(4)

• Complexity and monotonicity results for domination games
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• Dual domination problems in graphs
• Approximability of open \(k\)-monopoly problems

This page was built for publication: Complexity of majority monopoly and signed domination problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414422)