Approximation Algorithms and Hardness for Domination with Propagation
From MaRDI portal
Publication:5901134
DOI10.1137/06066672XzbMath1209.68628MaRDI QIDQ5901134
Publication date: 27 August 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
planar graphsdominating setapproximation algorithmsgreedy algorithmshardness of approximationtree-widthPMU placement problempower dominating set
Related Items
Hybrid search for the optimal PMU placement problem on a power grid, On the harmless set problem parameterized by treewidth, Techniques for determining equality of the maximum nullity and the zero forcing number of a graph, On the approximability of the minimum rainbow subgraph problem and other related problems, Power domination in circular-arc graphs, Connected power domination in graphs, An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}, Generalized power domination of graphs, Parameterized approximability of maximizing the spread of influence in networks, Generalized power domination: propagation radius and Sierpiński graphs, On some tractable and hard instances for partial incentives and target set selection, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, Power domination with bounded time constraints, \(k\)-power domination in block graphs, The \(k\)-power domination problem in weighted trees, Algorithms and Complexity of Power Domination in Graphs, Disproofs of three conjectures on the power domination of graphs, Power domination in regular claw-free graphs, The complexity of finding harmless individuals in social networks, Vertex sequences in graphs, Minimum Power Dominating Sets of Random Cubic Graphs, Generalized power domination in claw-free regular graphs