Approximability of open \(k\)-monopoly problems

DOI10.1007/s00224-020-10027-4OpenAlexW3120100068MaRDI QIDQ2048211

Sounaka Mishra, Shijin Rajakrishnan, B. Arjuna Krishna

Publication date: 5 August 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10027-4

zbMATH Keywords

dominating setapproximation algorithmsopen \(k\)-monopolies

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Approximation algorithms (68W25) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of majority monopoly and signed domination problems
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• The node-deletion problem for hereditary properties is NP-complete
• Optimization, approximation, and complexity classes
• Rounding algorithms for covering problems
• Some APX-completeness results for cubic graphs
• The power of small coalitions in graphs
• Open k-monopolies in graphs: complexity and related concepts
• A threshold of ln n for approximating set cover