论文标题
用度约束或直径约束对跨越树的重新配置
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
论文作者
论文摘要
我们研究了通过一系列边缘翻转序列在同一图中找到从给定的跨越树到另一个给定的跨越树的转换的复杂性。 Matroid碱基的交换属性会立即产生，如果我们对跨越树没有限制，这种转换总是存在。在本文中，我们希望找到一种仅通过满足某些约束的树木的转换。我们的重点是界定跨树木的最高度或直径，我们给出以下结果。在多项式时间内可以解决下界限的问题，而最大程度上限制的问题是PSPACE完整的。直径下限的问题是NP硬化，而直径上限的问题在多项式时间内可以溶解。
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.
