Abstract | ||
---|---|---|
This paper considers synchronous discrete-time dynamical systems on graphs based on the threshold model. It is well known that after a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of finding the fixed points for this type of dynamical system is in general both NP-hard and #P-complete. In this paper we give a surprisingly simple graph-theoretic characterization of fixed points and 2-cycles for the class of finite trees. Thus, the class of trees is the first nontrivial graph class for which a complete characterization of fixed points exists. This characterization enables us to provide bounds for the total number of fixed points and pure 2-cycles. It also leads to an output-sensitive algorithm to efficiently generate these states. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1007/978-3-031-09993-9_15 | Colloquium on Structural Information & Communication Complexity (SIROCCO) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Volker Turau | 1 | 12 | 2.17 |