| 基于顶点度数的完全独立生成树研究 |
| |
| 引用本文： | 林政宽,赵源,樊建席,程宝雷.基于顶点度数的完全独立生成树研究[J].计算机科学,2017,44(6):94-96, 107. |
| |
| 作者姓名： | 林政宽 赵源 樊建席 程宝雷 |
| |
| 作者单位： | 苏州大学计算机科学与技术学院 苏州215006,苏州大学计算机科学与技术学院 苏州215006,苏州大学计算机科学与技术学院 苏州215006,苏州大学计算机科学与技术学院 苏州215006;江苏省计算机信息处理技术重点实验室 苏州215006 |
| |
| 基金项目： | 本文受国家自然科学基金项目(61572340,61572337),江苏省高校自然科学研究面上项目(14KJB520034),中国博士后科学基金面上项目(2015M581858),2015年度“江苏省博士后科研资助 |
| |
| 摘 要： | 在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T1,T2,…,Tn,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs)。在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n－2,那么,G中存在至少 n/3 棵CISTs1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n(n≥5) 个顶点的任意图G,假设图G的最小顶点度数至少为n－2,得出度数为n－2的顶点的个数、度数为n－1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献1]中的结果。
|
| 关 键 词： | 完全独立生成树 可靠传输 互连网络 图 |
| 收稿时间： | 2016/5/21 0:00:00 |
| 修稿时间： | 2016/7/14 0:00:00 |
Research on Completely Independent Spanning Trees Based on Degree of Vertices |
| |
| LIN Cheng-kuan,ZHAO Yuan,FAN Jian-xi and CHENG Bao-lei.Research on Completely Independent Spanning Trees Based on Degree of Vertices[J].Computer Science,2017,44(6):94-96, 107. |
| |
| Authors: | LIN Cheng-kuan ZHAO Yuan FAN Jian-xi and CHENG Bao-lei |
| |
| Affiliation: | School of Computer Science and Technology,Suzhou 215006,China,School of Computer Science and Technology,Suzhou 215006,China,School of Computer Science and Technology,Suzhou 215006,China and School of Computer Science and Technology,Suzhou 215006,China;Provincial Key Laboratory for Computer Information Processing Technology, Suzhou 215006,China |
| |
| Abstract: | |
| |
| Keywords: | Completely independent spanning trees Reliable transmission Interconnection network Graph |
|
|
点击此处可从《计算机科学》下载全文 |
|
