Generalized threshold processes on graphs

DOI10.1016/J.TCS.2017.05.010MaRDI QIDQ2402258zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Uéverton S. Souza, Carlos Vinícius G. C. Lima, Jayme L. Szwarcfiter

Publication date 7 September 2017

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

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

zbMATH Keywords

target setdynamic monopolyirreversible threshold processes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Irreversible conversion of graphs
• Reversible iterative graph processes
• Irreversible 2-conversion set in graphs of bounded degree
• Irreversible conversion processes with deadlines
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
• A threshold of ln n for approximating set cover
• An upper bound for thek-domination number of a graph
• Analytical approach to parallel repetition
• Approximation hardness of dominating set problems in bounded degree graphs
• Combinatorial model and bounds for target set selection
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• Irreversible conversion processes with deadlines
• Latency-bounded target set selection in social networks
• Metastability effects in bootstrap percolation
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On dynamic monopolies of graphs with general thresholds
• On general frameworks and threshold functions for multiple domination
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the approximability of influence in social networks
• Onk-domination and minimum degree in graphs
• Random majority percolation
• Remarks on dynamic monopolies with given average thresholds
• Spread of influence in weighted networks under time and budget constraints
• The power of small coalitions in graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(7)

• scientific article; zbMATH DE number 7650133 (Why is no real title available?)
• Iterated open neighborhood graphs and generalizations
• A computational study of \(f\)-reversible processes on graphs
• On \(f\)-reversible processes on graphs
• Reversible iterative graph processes
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• Irreversible \(k\)-threshold conversion number of circulant graphs

This page was built for publication: Generalized threshold processes on graphs

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