近日,我院杨雨教授团队与其他单位合作,在中国计算机学会(CCF) A类国际顶级期刊《Information and Computation》上发表了题为“Exact Counting of Subtrees With Diameter No More Than d in Trees: A Generating Function Approach”的研究论文。杨雨博士为论文第一作者,平顶山学院为第一单位。

该研究围绕“子树枚举”这一经典难题取得三项重要突破:首次构建了含 (d+2) 个变量的新型生成函数,实现了对固定顶点根化子树的高效精确计数,为算法设计奠定理论基础;基于该函数设计出递归精确计数算法,将直径不超过 d 的子树的计数时间复杂度优化至 O(dn²),显著优于已有方法;研究还拓展了经典理论框架,将Frank Ruskey教授于1981年提出的树子树计数工作纳入统一体系,使其成为本研究在直径取极值时的特例。
研究成果不仅在理论计算机科学和图论领域具有重要学术价值,更在生物信息学(如蛋白质与DNA序列比对、分子活性预测、生物网络模体识别)、新材料研发与药物分子设计等多个前沿方向展现出广泛的应用潜力,为计算机科学、化学、材料科学及药学等跨学科研究提供了基础性方法与工具支撑。
此项成果实现了平顶山学院以第一单位在理论计算机科学CCF-A类出版物上发表论文的零的突破,标志着学校在图计算、算法分析与设计等领域的科研水平获得国际前沿和同行专家的高度认可。这也是学校深入贯彻落实“大三步走”与“小三步走”发展战略取得的一项重要阶段性进展,为我校计算机科学与技术、电子信息两个硕士点的建设提供了高水平科研成果的有力支撑。

《Information and Computation》(IANDC)是中国计算机学会(CCF)认定的理论计算机科学领域A类顶级期刊(该方向A类期刊仅有三个),以审稿严谨、对原创性要求极高著称,该刊近五年平均每年发表论文不足百篇,国内发表单位多为北京大学,中科院等知名高校与科研机构。
本研究得到了河南省大气细颗粒物(PM2.5)分子多维拓扑及致癌特性分析国际联合实验室、国家自然科学基金、河南省国际科技合作项目及河南省科技攻关项目等多个基金支持。
论文链接:
https://www.sciencedirect.com/science/article/pii/S0890540125000896