Minimum monopoly in regular and tree graphs

DOI10.1016/j.disc.2005.06.036zbMath1116.05080OpenAlexW2106101701MaRDI QIDQ2497525

Yanyan Li

Publication date: 4 August 2006

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.06.036

zbMATH Keywords

algorithmsAPX-completeminimum monopoly

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A study of monopolies in graphs ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs

Cites Work

• Completeness in approximation classes
• A fast approximation algorithm for the multicovering problem
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Fault-local distributed mending (extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item