Irreversible conversion of graphs

DOI10.1016/j.tcs.2011.03.029zbMath1220.05109OpenAlexW2030703286MaRDI QIDQ551200

Dieter Rautenbach, Carmen C. Centeno, Mitre C. Dourado, Lucia Draque Penso, Jayme Luiz Szwarcfiter

Publication date: 14 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.03.029

zbMATH Keywords

spread of disease fault propagation dynamic monopoly catastrophic fault pattern irreversible threshold process local majority process

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity aspects of the triangle path convexity ⋮ $P_3$-hull number of graphs with diameter two ⋮ On the $P_3$-hull number of some products of graphs ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ Vaccinate your trees! ⋮ Optimizing Spread of Influence in Social Networks via Partial Incentives ⋮ On the harmless set problem parameterized by treewidth ⋮ A general framework for path convexities ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ Computing the hull number in toll convexity ⋮ On the $\Delta $-interval and the $\Delta $-convexity numbers of graphs and graph products ⋮ Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ Algorithmic and structural aspects of the $P_3$-Radon number ⋮ Generalized threshold processes on graphs ⋮ ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS ⋮ $P_3$-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results ⋮ On the Carathéodory number of interval and graph convexities ⋮ Irreversible $k$-threshold conversion number of circulant graphs ⋮ The maximum time of 2-neighbor bootstrap percolation: complexity results ⋮ Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ On the monophonic rank of a graph ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ On the hull number on cycle convexity of graphs ⋮ Target set selection with maximum activation time ⋮ Complexity analysis of $P_3$-convexity problems on bounded-degree and planar graphs ⋮ Solving target set selection with bounded thresholds faster than $2^n$ ⋮ Characterization and recognition of Radon-independent sets in split graphs ⋮ Complete characterizations of the 2-domination and $\mathcal{P}_3$-hull number polytopes ⋮ Irreversible k-threshold conversion number of some graphs ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ An upper bound on the $P_3$-Radon number ⋮ Irreversible conversion processes with deadlines ⋮ Latency-bounded target set selection in social networks ⋮ Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks ⋮ The Carathéodory number of the $P_3$ convexity of chordal graphs ⋮ Computing the $\mathcal{P}_3$-hull number of a graph, a polyhedral approach ⋮ Active influence spreading in social networks ⋮ Graphs with few $P_4$'s under the convexity of paths of order three ⋮ Inapproximability results for graph convexity parameters ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ On the complexity of the $P_{3}$-hull number of the Cartesian product of graphs ⋮ Complexity properties of complementary prisms ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ A computational study of $f$-reversible processes on graphs ⋮ Reversible iterative graph processes ⋮ Constant thresholds can make target set selection tractable ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Vector domination in split-indifference graphs ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs ⋮ Whom to befriend to influence people ⋮ Fast and frugal targeting with incentives ⋮ Partial immunization of trees ⋮ Evangelism in Social Networks ⋮ The hull number in the convexity of induced paths of order $3$ ⋮ The complexity of finding harmless individuals in social networks ⋮ Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms ⋮ Influence diffusion in social networks under time window constraints ⋮ The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects ⋮ Spread of influence in weighted networks under time and budget constraints ⋮ Influence Diffusion in Social Networks under Time Window Constraints ⋮ On irreversible spread of influence in edge-weighted graphs ⋮ On reconfigurability of target sets

Cites Work