论文标题
图形ft的跨越树的枢轴灰色代码。
Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan
论文作者
论文摘要
我们考虑列出图$ g $的所有跨越树的问题，以使连续的树通过在顶点周围旋转单个边缘而有所不同。这样的清单称为“枢轴灰色代码”，它的条件比已知的“旋转门”灰色代码更严格。大多数旋转门算法都采用标准的边缘缺失/边缘收缩递归方法，我们证明，在需要“枢轴”属性时，我们表现出自然挑战。我们的主要结果是发现了一种贪婪的策略，该策略在枢轴灰色代码顺序中列出了风扇图的跨越树。这是第一种使用如此最小的更改操作详尽生成跨越树的贪婪算法。然后研究结果清单，以找到一种递归算法，该算法在$ o（1）$ - 使用$ o（n）$ space中产生相同的列表。此外，我们提出了$ o（n）$ - 时间算法，用于排名和不合格我们的列表；对通用$ O（n^3）$ - 时间算法的改进，用于排名和跨越任意图的不明式的跨度。最后，我们讨论如何应用清单以找到轮子图的枢轴灰色代码。
We consider the problem of listing all spanning trees of a graph $G$ such that successive trees differ by pivoting a single edge around a vertex. Such a listing is called a "pivot Gray code", and it has more stringent conditions than known "revolving-door" Gray codes for spanning trees. Most revolving-door algorithms employ a standard edge-deletion/edge-contraction recursive approach which we demonstrate presents natural challenges when requiring the "pivot" property. Our main result is the discovery of a greedy strategy to list the spanning trees of the fan graph in a pivot Gray code order. It is the first greedy algorithm for exhaustively generating spanning trees using such a minimal change operation. The resulting listing is then studied to find a recursive algorithm that produces the same listing in $O(1)$-amortized time using $O(n)$ space. Additionally, we present $O(n)$-time algorithms for ranking and unranking the spanning trees for our listing; an improvement over the generic $O(n^3)$-time algorithm for ranking and unranking spanning trees of an arbitrary graph. Finally, we discuss how our listing can be applied to find a pivot Gray code for the wheel graph.
