论文标题
分布式树木的分布式重新配置
Distributed Reconfiguration of Spanning Trees
论文作者
论文摘要
在重新配置问题中，给定问题和两个可行的解决方案，任务是找到一系列转换序列，从一个解决方案到另一种解决方案，以使每个中间状态也是对问题的可行解决方案。在本文中，我们研究了分布式树的重新配置问题，并定义了一个新的重新配置步骤，称为$ k $ -simultanate的添加和删除，其中允许每个节点最多添加$ k $ edge，并在最多$ k $ edge上删除$ k $的边缘，例如多个节点不会添加或删除相同的边缘。 我们首先观察到，如果两个输入跨越树是扎根的，那么我们可以使用单个$ 1 $ -Simultanate的添加和删除在Escest模型中的一轮中进行重新配置。因此，我们将注意力集中在无根的跨越树上，并表明使用单个$ 1 $ simultanate的添加和删除步骤将无根的生成树转变为另一个，并需要$ω（n）$ rounds在本地模型中。我们还表明，可以使用单个$ 2 $的添加添加和删除步骤将一个未根的生成树转换为另一个，可以在$ O（\ log n）$ rounds中进行，在Electest模型中。
In a reconfiguration problem, given a problem and two feasible solutions of the problem, the task is to find a sequence of transformations to reach from one solution to the other such that every intermediate state is also a feasible solution to the problem. In this paper, we study the distributed spanning tree reconfiguration problem and we define a new reconfiguration step, called $k$-simultaneous add and delete, in which every node is allowed to add at most $k$ edges and delete at most $k$ edges such that multiple nodes do not add or delete the same edge. We first observe that, if the two input spanning trees are rooted, then we can do the reconfiguration using a single $1$-simultaneous add and delete step in one round in the CONGEST model. Therefore, we focus our attention towards unrooted spanning trees and show that transforming an unrooted spanning tree into another using a single $1$-simultaneous add and delete step requires $Ω(n)$ rounds in the LOCAL model. We additionally show that transforming an unrooted spanning tree into another using a single $2$-simultaneous add and delete step can be done in $O(\log n)$ rounds in the CONGEST model.
