A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph

DOI10.1007/978-3-030-89543-3_5arXiv2108.09363MaRDI QIDQ6375708FDOQ6375708

Authors: Ben Cameron, Aaron Grubb, Joe Sawada 

Publication date: 20 August 2021

Abstract: 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.

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

This page was built for publication: A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6375708)