Fixed points and 2-cycles of synchronous dynamic coloring processes on trees

Publikationstyp
Conference Paper
Date Issued
2022-06-25
Sprache
English
Author(s)
Turau, Volker  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/13430
First published in
Lecture notes in computer science  
Number in series
13298 LNCS
Start Page
265
End Page
282
Citation
29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022)
Contribution to Conference
29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022  
Publisher DOI
10.1007/978-3-031-09993-9_15
Scopus ID
2-s2.0-85134316371
Publisher
Springer International Publishing
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.
DDC Class
004: Informatik