Solving target set selection with bounded thresholds faster than \(2^n\)
DOI10.1007/s00453-022-01031-wOpenAlexW2940787716MaRDI QIDQ2684482
Ivan A. Bliznets, Danil Sagunov
Publication date: 16 February 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01031-w
target set selectionsocial influenceexact exponential algorithmsbootstrap percolationirreversible conversions of graphsvertex thresholds
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial model and bounds for target set selection
- Treewidth governs the complexity of target set selection
- Enumerating minimal subset feedback vertex sets
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Scheduling partially ordered jobs faster than \(2^n\)
- Irreversible conversion of graphs
- Exact exponential algorithms.
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Parameterized graph separation problems
- Solving connected dominating set faster than \(2^n\)
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Size bounds for dynamic monopolies
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Parameterized approximability of maximizing the spread of influence in networks
- Constant thresholds can make target set selection tractable
- Largest Chordal and Interval Subgraphs Faster Than 2 n
- Exact Algorithm for the Maximum Induced Planar Subgraph Problem
- The traveling salesman problem in bounded degree graphs
- Capacitated Domination Faster Than O(2 n )
- On the Approximability of Influence in Social Networks
- Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
- Bootstrap Percolation in High Dimensions
- Target Set Selection Parameterized by Clique-Width and Maximum Threshold
This page was built for publication: Solving target set selection with bounded thresholds faster than \(2^n\)
