Approximability of open \(k\)-monopoly problems
type: Item
instance of: scholarly article
title: Approximability of open \(k\)-monopoly problems
author: Sounaka Mishra
author: B. Arjuna Krishna
author: Shijin Rajakrishnan
published in: Theory of Computing Systems
publication date: 2021-08-05T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90Cxx
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 7379116
zbMATH Keywords: open \(k\)-monopolies
zbMATH Keywords: dominating set
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: s00224-020-10027-4
OpenAlex ID: W3120100068
cites work: Some APX-completeness results for cubic graphs
cites work: The power of small coalitions in graphs
cites work: Rounding algorithms for covering problems
cites work: A threshold of ln n for approximating set cover
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Q4820818
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Complexity of majority monopoly and signed domination problems
cites work: Q4415262
cites work: Optimization, approximation, and complexity classes
cites work: Q5488895
cites work: Open k-monopolies in graphs: complexity and related concepts
DOI: 10.1007/S00224-020-10027-4
description: scientific article; zbMATH DE number 7379116