A loopless algorithm for generating (K,M)-ary trees in gray-code order

Yu Hsuan Chang, Ro Yu Wu, Cheng Kuan Lin, Jou Ming Chang*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Introduced by Du and Liu in 2007, a (k, m)-ary tree is a generalization of k-ary tree such that the nodes have degree k on even levels and the nodes have degree 0 or m on odd levels. Especially, every node with the degree m on odd levels is called a crucial node. In a (k, m)-ary tree of order n, there are exactly n crucial nodes. A loopless algorithm is an algorithm for generating combinatorial objects using only assignment and comparison statements and does not include loop structure or recursion. In this paper, we propose a loopless algorithm to generate (k, m)-ary trees of order n in Gray-code order using Z-sequence suggested by Zaks in 1980. The required memory space of our algorithm is (formula presented). Moreover, we analyze both amortized costs of assignment statements and comparison statements, which are no more than (formula presented) and (formula presented), respectively.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 14th International Workshop, FAW 2020, Proceedings
EditorsMinming Li
PublisherSpringer Science and Business Media Deutschland GmbH
Pages121-132
Number of pages12
ISBN (Print)9783030599003
DOIs
StatePublished - 2020
Event14th International Workshop on Frontiers in Algorithmics, FAW 2020 - Haikou, China
Duration: 19 Oct 202021 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12340 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Workshop on Frontiers in Algorithmics, FAW 2020
Country/TerritoryChina
CityHaikou
Period19/10/2021/10/20

Keywords

  • (k, m)-ary trees
  • Amortized analysis
  • Gray-codes
  • Loopless algorithms
  • Zaks’ sequences

Fingerprint

Dive into the research topics of 'A loopless algorithm for generating (K,M)-ary trees in gray-code order'. Together they form a unique fingerprint.

Cite this