On enumerating algorithms of novel multiple leaf-distance granular regular ?-subtrees of trees

作者：Yang, Yu; Liu, Hongbo^*; Wang, Hua; Zhang, Xiao-Dong^*; Chen, C. L. Philip

来源：Information and Computation, 2022, 289.

DOI：10.1016/j.ic.2022.104942

• Leaf-distance granular regular?-subtree
• (LDR?-subtree)
• Weight
• Enumeration
• Generating function
• Algorithm

Subtrees and BC-subtrees (subtrees in which the distance between any two leaves is even) are important concepts in the study of complex graphical structures. In this article, we propose a novel generalization called the leaf-distance granular regular alpha-tree (abbreviated as LDR alpha-tree for short). This is a tree in which the distance between any two leaves is divisible by alpha (alpha is a positive integer). A LDR alpha-subtree is simply a subtree that is also a LDR alpha-tree. We present basic properties and generating functions related to the LDR alpha- subtrees enumeration. Based on those theoretical results we provide efficient algorithms for enumerating various LDR alpha-subtrees of trees. Our algorithms can serve as multi-distance granularity sifters of a graph to screen all the alpha-subtree uniformly, and thus provide novel insights into exploring new structural properties from the perspective of multiple leaf -distance granularity.

• 单位
  上海交通大学