On the approximability of positive influence dominating set in social networks

DOI10.1007/s10878-012-9530-7zbMath1322.90105OpenAlexW2069808479MaRDI QIDQ2015789

Yilin Shen, My T. Thai, Thang N. Dinh, Dung Tien Nguyen

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9530-7

zbMATH Keywords

approximation algorithmsocial networksinformation diffusionhardness of approximation

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Related Items (19)

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 ⋮ A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem ⋮ Local ratio method on partial set multi-cover ⋮ The connected critical node problem ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ A compact mixed integer linear formulation for safe set problems ⋮ Computing an effective decision making group of a society using social network analysis ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ On positive-influence target-domination ⋮ Connected positive influence dominating set in \(k\)-regular graph ⋮ Alliances in graphs of bounded clique-width ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ Positive influence domination in graphs ⋮ On the complexity of the vector connectivity problem

Cites Work

• Polynomial time approximation scheme for \(t\)-latency bounded information propagation problem in wireless networks
• New dominating sets in social networks
• On the hardness of optimization in power-law graphs
• Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
• A threshold of ln n for approximating set cover
• A random graph model for massive graphs
• Positive Influence Dominating Set in Online Social Networks
• Community structure in social and biological networks
• Non-approximability results for optimization problems on bounded degree instances
• Algorithms – ESA 2004
• Automata, Languages and Programming

This page was built for publication: On the approximability of positive influence dominating set in social networks