Approximability of open k-monopoly problems

DOI10.1007/S00224-020-10027-4OpenAlexW3120100068MaRDI QIDQ2048211FDOQ2048211

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

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\)

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)

Cites Work

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

Cited In (4)

• Complexity of majority monopoly and signed domination problems
• Title not available (Why is that?)
• 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)