Cameron et al. [27th Int. Conf. Computing and Combinatorics (COCOON 2021), LNCS 13025, pp. 49-60] recently presented an algorithm for generating all spanning trees of a fan graph in O(1)amortized time. The listing of ...
详细信息
ISBN:
(纸本)9783031185298;9783031185304
Cameron et al. [27th Int. Conf. Computing and Combinatorics (COCOON 2021), LNCS 13025, pp. 49-60] recently presented an algorithm for generating all spanning trees of a fan graph in O(1)amortized time. The listing of spanning trees fulfills the so-called pivot Gray code property so that successive trees differ by pivoting a single edge around a vertex. They also presented algorithms for ranking and unranking a spanning tree in the listing in O(n) time using O(n) space. In this paper, we first observe that all spanning trees of a fan graph can be naturally represented by integer sequences so that their coding tree has properties with regularity. Then, we propose a simple algorithm for generating spanning-tree sequences in lexicographic order in O(1)amortized time according to these properties. Additionally, based on the lexicographic order, we develop ranking and unrankingalgorithms in O(n)-time using n + O(1) space (i.e., the size of the space is just slightly larger than n).
暂无评论