On the hardness of approximating minimum monopoly problems

DOI10.1007/3-540-36206-1_25MaRDI QIDQ4415262zbMATH OpenFDO

Authors Sounaka Mishra, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian

Publication date 28 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2556/25560277.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximability of open \(k\)-monopoly problems
• Minimum monopoly in regular and tree graphs
• Complexity of majority monopoly and signed domination problems
• Max- and Min-neighborhood monopolies
• Approximating the domatic number

Cited in

(15)

• Max- and Min-neighborhood monopolies
• Alliances in graphs of bounded clique-width
• Approximability of open \(k\)-monopoly problems
• Alliance free sets in Cartesian product graphs
• Minimum monopoly in regular and tree graphs
• On the hardness of approximating the min-hack problem
• Max- and min-neighborhood monopolies
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• A note on anti-coordination and social interactions
• Complexity of majority monopoly and signed domination problems
• Hardness Results for Seeding Complex Contagion with Neighborhoods
• Majority vote in social networks
• On the complexity of co-secure dominating set problem
• Target set in threshold models
• Opinion diffusion in graphs: an adversarial approach

This page was built for publication: On the hardness of approximating minimum monopoly problems

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