A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph
share
We use a greedy strategy to list the spanning trees of the fan graph, F_n, such that successive trees differ by pivoting a single edge around a vertex. 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.
READ FULL TEXT