Approximability of open k-monopoly problems

DOI10.1007/S00224-020-10027-4MaRDI QIDQ2048211zbMATH OpenOpenAlexFDO

Authors Sounaka Mishra, B. Arjuna Krishna, Shijin Rajakrishnan

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

approximation algorithmsdominating setopen \(k\)-monopolies

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1954391
• Minimum monopoly in regular and tree graphs
• Complexity of majority monopoly and signed domination problems
• The complexity of open \(k\)-monopolies in graphs for negative \(k\)

Cites work

• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• scientific article; zbMATH DE number 5056647 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Complexity of majority monopoly and signed domination problems
• Efficient bounds for the stable set, vertex cover and set packing problems
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Optimization, approximation, and complexity classes
• Rounding algorithms for covering problems
• Some APX-completeness results for cubic graphs
• The node-deletion problem for hereditary properties is NP-complete
• The power of small coalitions in graphs

Cited in

(4)

• Complexity of majority monopoly and signed domination problems
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• A property of solutions to linear monopoly problems
• The complexity of open \(k\)-monopolies in graphs for negative \(k\)

This page was built for publication: Approximability of open \(k\)-monopoly problems

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