The complexity of finding harmless individuals in social networks

DOI10.1016/J.DISOPT.2014.09.004MaRDI QIDQ2339843zbMATH OpenOpenAlexFDO

Authors Cristina Bazgan, Morgan Chopin

Publication date 9 April 2015

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2014.09.004

zbMATH Keywords

social networkstreewidthapproximationparameterized complexityharmless set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30)

Recommendations

• The robust set problem: parameterized complexity and approximation
• On positive influence dominating sets in social networks
• Parameterized inapproximability of target set selection and generalizations
• Parameterized inapproximability of target set selection and generalizations
• Parameterized complexity of safe set

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A survey on alliances and related parameters in graphs
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximation Algorithms and Hardness for Domination with Propagation
• Approximation algorithms for NP-complete problems on planar graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Constant thresholds can make target set selection tractable
• Domination in Graphs Applied to Electric Power Networks
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• Local majorities, coalitions and monopolies in graphs: A review
• Networks, crowds and markets. Reasoning about a highly connected world.
• On Syntactic versus Computational Views of Approximability
• On the approximability of influence in social networks
• Optimization, approximation, and complexity classes
• Parameterized approximability of maximizing the spread of influence in networks
• Parameterized complexity of generalized domination problems
• Parametrized complexity theory.
• SOFSEM 2006: Theory and Practice of Computer Science
• Some results on the target set selection problem
• The Turing way to parameterized complexity
• The robust set problem: parameterized complexity and approximation
• Total domination in graphs
• Total domination in graphs
• Treewidth governs the complexity of target set selection
• Treewidth. Computations and approximations
• Variants of spreading messages
• k-tuple total domination in graphs

Cited in

(6)

• A parameterized complexity view on collapsing \(k\)-cores
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• The robust set problem: parameterized complexity and approximation
• On the harmless set problem parameterized by treewidth
• Harmless sets in sparse classes
• On Structural Parameterizations of the Harmless Set Problem

This page was built for publication: The complexity of finding harmless individuals in social networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339843)