摘要
设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ＞０整数．Ｇ中存在生成树Ｔ，使得Δ（Ｔ）小于ｄ吗？这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法．本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅ时，则有Ｏ（ｎ２）的算法求出Ｇ的生成树Ｔ，使Δ（Ｔ）≤ｒ。
For a positive integer d , the problem of whether a connected graph contains a spanning tree T with Δ(T)≤d is NP Complete Therefore there is unlikely to have polynomial algorithm to solve such problem in general graph This paper gives an O(n 2) algorithm for finding a spanning tree with Δ(T)≤r in connected K 1,r free graphs
出处
《纯粹数学与应用数学》
CSCD
1996年第2期100-103,共4页
Pure and Applied Mathematics
