On positive influence dominating sets in social networks

DOI10.1016/j.tcs.2009.10.001zbMath1233.90272OpenAlexW1984588599MaRDI QIDQ621845

Erika T. Camacho, Feng Wang, Kuai Xu, Shan Shan, Hongwei David Du, Won Jun Lee, Yan Shi

Publication date: 28 January 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.10.001

zbMATH Keywords

social networksdominating setAPX-hardpositive influence dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (18)

An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks ⋮ A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ Local ratio method on partial set multi-cover ⋮ Weighted target set selection on trees and cycles ⋮ A unified greedy approximation for several dominating set problems ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ Approximation algorithm for partial set multicover versus full set multicover ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ Connected positive influence dominating set in \(k\)-regular graph ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Positive influence domination in graphs ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Design and analysis of approximation algorithms
• An analysis of the greedy algorithm for the submodular set covering problem
• On the hardness of optimization in power-law graphs
• A BETTER APPROXIMATION FOR MINIMUM AVERAGE ROUTING PATH CLUSTERING PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Positive Influence Dominating Set in Online Social Networks
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

This page was built for publication: On positive influence dominating sets in social networks