Generating Spanning Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms
Ro-Yu Wu  1@  , Cheng-Chia Tseng  2@  , Ling-Ju Hung  3@  , Jou-Ming Chang  2, *@  
1 : Department of Industrial Management, Lunghwa University of Science and Technology
2 : Institute of Information and Decision Sciences, National Taipei University of Business
3 : Department of Product Innovation and Entrepreneurship, National Taipei University of Business
* : Corresponding author

Cameron et al. recently presented an algorithm for generating all spanning trees of a fan graph that fulfill the so-called pivot Gray code property in O(1)-amortized time. They also presented algorithms for ranking and unranking a spanning tree in the listing in O(n) time using O(n) space. This paper first observes that all spanning trees of a fan graph can be naturally represented by integer sequences with regular properties. 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 unranking algorithms in O(n)-time using n+O(1) space.


Online user: 1 Privacy
Loading...