Solving Target Set Selection with Bounded Thresholds Faster than 2^n
From MaRDI portal
Publication:5009485
DOI10.4230/LIPIcs.IPEC.2018.22OpenAlexW2962912836MaRDI QIDQ5009485
Danil Sagunov, Ivan A. Bliznets
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1807.10789
social influencetarget setexact exponential algorithmsbootstrap percolationirreversible conversions of graphsvertex thresholds
Related Items (4)
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ Enumeration of minimal tropical connected sets ⋮ Target set selection parameterized by vertex cover and more
Cites Work
- 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
