Tight Bounds on the Minimum Size of a Dynamic Monopoly

Ahad N. Zehmakan

doi:10.1007/978-3-030-13435-8_28

Tight Bounds on the Minimum Size of a Dynamic Monopoly

Ahad N. Zehmakan

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

8 Citations (Scopus)

Abstract

Assume that you are given a graph G = (V,E) with an initial
coloring, where each node is black or white. Then, in discrete-time rounds
all nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way r-bootstrap percolation, for
some integer r, if a node with at least r black neighbors gets black and
white otherwise. Similarly, in two-way α-bootstrap percolation, for some
0 <α< 1, a node gets black if at least α fraction of its neighbors are
black, and white otherwise. The two aforementioned processes are called
respectively r-bootstrap and α-bootstrap percolation if we require that
a black node stays black forever.
For each of these processes, we say a node set D is a dynamic monopoly
whenever the following holds: If all nodes in D are black then the graph
gets fully black eventually. We provide tight upper and lower bounds on
the minimum size of a dynamic monopoly.

Original language	English
Title of host publication	Language and Automata Theory and Applications
Subtitle of host publication	13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings
Publisher	Springer Cham
Pages	381-393
ISBN (Print)	978-3-030-13434-1
DOIs	https://doi.org/10.1007/978-3-030-13435-8_28
Publication status	Published - 2019
Externally published	Yes
Event	13th International Conference on Language and Automata Theory and Applications - St. Petersburg, Russian Federation Duration: 26 Mar 2019 → 29 Mar 2019

Conference

Conference	13th International Conference on Language and Automata Theory and Applications
Abbreviated title	LATA 2019
Country/Territory	Russian Federation
City	St. Petersburg
Period	26/03/19 → 29/03/19

Access to Document

10.1007/978-3-030-13435-8_28

https://dblp.org/rec/conf/lata/Zehmakan19

Cite this

@inproceedings{5d60607edada41ad96650aa2bbadb75f,

title = "Tight Bounds on the Minimum Size of a Dynamic Monopoly",

abstract = "Assume that you are given a graph G = (V,E) with an initialcoloring, where each node is black or white. Then, in discrete-time roundsall nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way r-bootstrap percolation, forsome integer r, if a node with at least r black neighbors gets black andwhite otherwise. Similarly, in two-way α-bootstrap percolation, for some0 <α< 1, a node gets black if at least α fraction of its neighbors areblack, and white otherwise. The two aforementioned processes are calledrespectively r-bootstrap and α-bootstrap percolation if we require thata black node stays black forever.For each of these processes, we say a node set D is a dynamic monopolywhenever the following holds: If all nodes in D are black then the graphgets fully black eventually. We provide tight upper and lower bounds onthe minimum size of a dynamic monopoly.",

author = "Zehmakan, {Ahad N.}",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; 13th International Conference on Language and Automata Theory and Applications, LATA 2019 ; Conference date: 26-03-2019 Through 29-03-2019",

year = "2019",

doi = "10.1007/978-3-030-13435-8_28",

language = "English",

isbn = "978-3-030-13434-1",

pages = "381--393",

booktitle = "Language and Automata Theory and Applications",

publisher = "Springer Cham",

}

Zehmakan, AN 2019, Tight Bounds on the Minimum Size of a Dynamic Monopoly. in Language and Automata Theory and Applications: 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings. Springer Cham, pp. 381-393, 13th International Conference on Language and Automata Theory and Applications, St. Petersburg, Russian Federation, 26/03/19. https://doi.org/10.1007/978-3-030-13435-8_28

TY - GEN

T1 - Tight Bounds on the Minimum Size of a Dynamic Monopoly

AU - Zehmakan, Ahad N.

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2019

Y1 - 2019

N2 - Assume that you are given a graph G = (V,E) with an initialcoloring, where each node is black or white. Then, in discrete-time roundsall nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way r-bootstrap percolation, forsome integer r, if a node with at least r black neighbors gets black andwhite otherwise. Similarly, in two-way α-bootstrap percolation, for some0 <α< 1, a node gets black if at least α fraction of its neighbors areblack, and white otherwise. The two aforementioned processes are calledrespectively r-bootstrap and α-bootstrap percolation if we require thata black node stays black forever.For each of these processes, we say a node set D is a dynamic monopolywhenever the following holds: If all nodes in D are black then the graphgets fully black eventually. We provide tight upper and lower bounds onthe minimum size of a dynamic monopoly.

AB - Assume that you are given a graph G = (V,E) with an initialcoloring, where each node is black or white. Then, in discrete-time roundsall nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way r-bootstrap percolation, forsome integer r, if a node with at least r black neighbors gets black andwhite otherwise. Similarly, in two-way α-bootstrap percolation, for some0 <α< 1, a node gets black if at least α fraction of its neighbors areblack, and white otherwise. The two aforementioned processes are calledrespectively r-bootstrap and α-bootstrap percolation if we require thata black node stays black forever.For each of these processes, we say a node set D is a dynamic monopolywhenever the following holds: If all nodes in D are black then the graphgets fully black eventually. We provide tight upper and lower bounds onthe minimum size of a dynamic monopoly.

U2 - 10.1007/978-3-030-13435-8_28

DO - 10.1007/978-3-030-13435-8_28

M3 - Conference Paper

SN - 978-3-030-13434-1

SP - 381

EP - 393

BT - Language and Automata Theory and Applications

PB - Springer Cham

T2 - 13th International Conference on Language and Automata Theory and Applications

Y2 - 26 March 2019 through 29 March 2019

ER -

Tight Bounds on the Minimum Size of a Dynamic Monopoly

Abstract

Conference

Access to Document

Fingerprint

Cite this