论文标题
树上的固定点和2个同步动态着色过程
Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees
论文作者
论文摘要
本文考虑基于阈值模型在图形上的同步离散时间动态系统。众所周知，在有限数量的回合之后，这些系统要么达到固定点，要么进入2循环。通常，找到此类动力系统的固定点的问题通常是NP-HARD和＃P-Complete。在本文中，我们为有限树类提供了令人惊讶的简单的图形特征和2循环的固定点和2个周期。因此，树类是对固定点的完整表征的第一个非平凡图类。这种表征使我们能够为固定点和纯2循环的总数提供界限。它还导致对输出敏感算法有效生成这些状态。
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.
