Complexity of majority monopoly and signed domination problems
DOI10.1016/J.JDA.2011.12.019zbMATH Open1237.68090OpenAlexW2043113420MaRDI QIDQ414422FDOQ414422
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
Recommendations
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)
Cites Work
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- Optimization, approximation, and complexity classes
- Approximation algorithms for NP-hard problems.
- Complexity of approximating bounded variants of optimization problems
- Non-approximability results for optimization problems on bounded degree instances
- Improved performance of the greedy algorithm for partial cover
- Domination in graphs with minimum degree two
- Title not available (Why is that?)
- Signed domination in regular graphs
- Inequalities relating domination parameters in cubic graphs
- Title not available (Why is that?)
- Efficient bounds for the stable set, vertex cover and set packing problems
- Signed domination in regular graphs and set-systems
- On the signed domination in graphs
- Majority domination in graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- STACS 2005
Cited In (4)
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)
