Home > Archive > 2012 > Volume 2 Number 6 (Dec. 2012) >
IJMLC 2012 Vol.2(6): 767-770 ISSN: 2010-3700
DOI: 10.7763/IJMLC.2012.V2.233

A Ranking Algorithm of Non-Regular Trees in Gray-Code Order

Ro–Yu Wu, Jou–Ming Chang, and An–Hang Chen

Abstract—A non-regular tree T with a prescribed branching sequence is an ordered tree whose internal nodes are numbered from 1 to n in preorder such that every node in T has a prescribed number of children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we show that a ranking algorithm can be done in quadratic time provided a preprocessing in advance.

Index Terms—Loopless algorithms, ranking algorithms, lexico-graphic order, gray-code order; non-regular trees.

Ro-Yu Wu is with the Department of Industrial Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan. (e-mail:eric@mail.lhu.edu.tw)
Jou-Ming Chang and An-Hang Chen are with the Institute of Information and Decision Sciences, National Taipei College of Business, Taipei, Taiwan. (e-mail: spade@mail.ntcb.edu.tw; hang@mail.ntcb.edu.tw)

[PDF]

Cite: Ro–Yu Wu, Jou–Ming Chang, and An–Hang Chen, "A Ranking Algorithm of Non-Regular Trees in Gray-Code Order," International Journal of Machine Learning and Computing vol. 2, no. 6, pp. 767-770, 2012.

General Information

  • ISSN: 2010-3700 (Online)
  • Abbreviated Title: Int. J. Mach. Learn. Comput.
  • Frequency: Bimonthly
  • DOI: 10.18178/IJMLC
  • Editor-in-Chief: Dr. Lin Huang
  • Executive Editor:  Ms. Cherry L. Chen
  • Abstracing/Indexing: Inspec (IET), Google Scholar, Crossref, ProQuest, Electronic Journals Library.
  • E-mail: ijmlc@ejournal.net


Article Metrics