The complexity of finding harmless individuals in social networks
From MaRDI portal
Publication:2339843
DOI10.1016/j.disopt.2014.09.004zbMath1308.91134OpenAlexW2061324666MaRDI QIDQ2339843
Morgan Chopin, Cristina Bazgan
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
Related Items (4)
A parameterized complexity view on collapsing \(k\)-cores ⋮ On the harmless set problem parameterized by treewidth ⋮ Harmless sets in sparse classes ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized complexity of generalized domination problems
- Treewidth governs the complexity of target set selection
- Irreversible conversion of graphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- \(k\)-tuple total domination in graphs
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Optimization, approximation, and complexity classes
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Local majorities, coalitions and monopolies in graphs: A review
- The Turing way to parameterized complexity
- Some results on the target set selection problem
- Constant thresholds can make target set selection tractable
- Parametrized complexity theory.
- The Robust Set Problem: Parameterized Complexity and Approximation
- On the Approximability of Influence in Social Networks
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Total domination in graphs
- On Syntactic versus Computational Views of Approximability
- Approximation algorithms for NP-complete problems on planar graphs
- Domination in Graphs Applied to Electric Power Networks
- Total Domination in Graphs
- Parameterized Approximability of Maximizing the Spread of Influence in Networks
- A survey on alliances and related parameters in graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Variants of Spreading Messages
- SOFSEM 2006: Theory and Practice of Computer Science
- Approximation Algorithms and Hardness for Domination with Propagation
This page was built for publication: The complexity of finding harmless individuals in social networks
