A Linear-Time Algorithm for the Feasibility of Pebble Motion on Trees
A Linear-Time Algorithm for the Feasibility of Pebble Motion on Trees
复制标题
解决树上卵石运动可行性的线性时间算法
DOI：
10.1007/pl00009259
复制
发表时间：
1999
期刊：
影响因子：
1.1
通讯作者：
G. Persiano
中科院分区：
文献类型：
--
作者：
V. Auletta;A. Monti;Mimmo Parente;G. Persiano
抽象的。我们考虑以下卵石运动问题。我们得到了一个带有N顶点和两个布置的树T
$ \ cal r $和
$ \ cal s $ of K <n不同的鹅卵石编号为1，。 。 。，k在树的不同顶点上。鹅卵石可以沿着T的边缘移动，只要在任何给定时间，一个卵石都沿边缘行驶，而t的每个顶点最多包含一个卵石。我们被问到以下问题：是安排
$ \ cal s $可从
$ \ cal r $？ 我们提出了一种算法，该算法在输入两种基础上的两种k卵石上的排列中，在带有n个顶点的树上决定了时间o（n）是否可以彼此之间达到两种布置。我们还提供了一种算法，该算法在输入两个可触及的配置上返回一系列移动，将一种配置转换为另一种配置。树上的卵石运动问题具有各种应用，包括分布式系统中的内存管理，机器人运动计划和偏转路由。
Abstract. We consider the following pebble motion problem. We are given a tree T with n vertices and two arrangements
$\cal R$ and
$\cal S$ of k<n distinct pebbles numbered 1, . . ., k on distinct vertices of the tree. Pebbles can move along edges of T provided that at any given time at most one pebble is traveling along an edge and each vertex of T contains at most one pebble. We are asked the following question: Is arrangement
$\cal S$ reachable from
$\cal R$ ? We present an algorithm that, on input two arrangements of k pebbles on a tree with n vertices, decides in time O(n) whether the two arrangements are reachable from one another. We also give an algorithm that, on input two reachable configurations, returns a sequence of moves that transforms one configuration into the other. The pebble motion problem on trees has various applications including memory management in distributed systems, robot motion planning, and deflection routing.