Exact counting of subtrees with diameter no more than din trees: A generating function approach
文献类型：期刊论文
| 作者 | Yang, Yu1,2; Jin, Bang-Bang1; Sun, Xiaoming3; Zhang, Xiao-Dong2; Li, Bo1; Zhao, Kai1; Wang, Hua4 |
| 刊名 | INFORMATION AND COMPUTATION
 |
| 出版日期 | 2025-11-01 |
| 卷号 | 307页码:26 |
| 关键词 | Network motifs Subtree number Diameter constraint Generating function Algorithm |
| ISSN号 | 0890-5401 |
| DOI | 10.1016/j.ic.2025.105353 |
| 英文摘要 | Network motifs, regarded as fundamental building blocks, offer crucial insights into the structure and function of complex networks, with broad applications across disciplines including sociology, computer science, bioinformatics, chemoinformatics, and pharmaceutics. However, the identification of network motifs remains a significant and computationally challenging problem. Among various motifs, subtree enumeration has garnered substantial attention in recent years, particularly due to its relevance in network science and bioinformatics. For an n-vertex tree T, by introducing novel generating functions with (d + 2) variables, we propose an innovative algorithm for the exact enumeration of T's subtrees rooted at fixed vertex v, where the distance between v and the farthest leaf is k = 0, 1, ... , d, and the distance between any two leaves is no more than d. Building on this algorithm, we develop novel recursive algorithms for exact enumerating various diameter no more than d subtrees (abbreviated as DNMT-d subtrees) of T. As applications, we apply these algorithms to derive the number of DNMT-d subtrees in a full binary tree Bh with h >= 2 levels, and briefly discuss the density of DNMT-d subtrees in general trees. Our research generalizes the work of Frank Ruskey on Listing and Counting Subtrees of a Tree in 1981 and makes it a special case of our study where d equals the diameter of the tree T. Moreover, the proposed O(dn2) algorithms introduce new approaches for enumerating subtrees under diameter constraints and lay the groundwork for counting diameter-constrained subgraphs (motifs) in complex networks. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). |
| 资助项目 | National Natural Science Foundation of China[12371254] ; National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[11971311] ; National Natural Science Foundation of China[12161141003] ; Key Scientific and Technological Project of Henan Province, China[252102521077] ; Key Scientific and Technological Project of Henan Province, China[252102240118] ; Key Scientific and Technological Project of Henan Province, China[242102521023] ; Science and Technology Commission of Shanghai Municipality[22JC1403600] ; China Henan International Joint Laboratory for Multidimensional Topology and Carcinogenic Characteristics Analysis of Atmospheric Particulate Matter PM2.5 |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:001571262200001 |
| 出版者 | ACADEMIC PRESS INC ELSEVIER SCIENCE |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/41720]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Sun, Xiaoming |
| 作者单位 | 1.Pingdingshan Univ, Sch Software, Pingdingshan 467000, Peoples R China 2.Shanghai Jiao Tong Univ, Sch Math Sci, MOE LSC & SHE MAC, Shanghai 200240, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 4.Georgia Southern Univ, Dept Math Sci, Statesboro, GA 30460 USA |
| 推荐引用方式 GB/T 7714 | Yang, Yu,Jin, Bang-Bang,Sun, Xiaoming,et al. Exact counting of subtrees with diameter no more than din trees: A generating function approach[J]. INFORMATION AND COMPUTATION,2025,307:26. |
| APA | Yang, Yu.,Jin, Bang-Bang.,Sun, Xiaoming.,Zhang, Xiao-Dong.,Li, Bo.,...&Wang, Hua.(2025).Exact counting of subtrees with diameter no more than din trees: A generating function approach.INFORMATION AND COMPUTATION,307,26. |
| MLA | Yang, Yu,et al."Exact counting of subtrees with diameter no more than din trees: A generating function approach".INFORMATION AND COMPUTATION 307(2025):26. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。