最小度生成树的最大度算法

Maximum-degree algorithm for the minimum-degree spanning tree problem

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.

Minimum degree spanning tree problem is NP -hard. This paper presents a visual approximation algo- rithm for the Minimum Degree Spanning Tree problem ： To find the maximal degree vertex of graph G, and get rid of an edge incident to it from basic cycle, and so on, until the maximum degree of the graph G is not in any basic cir- cle, as there are other basic circle, get rid of an edge from the basic circle, then get a spanning tree. The algorithm gives a spanning tree of a degree at most one from the optimal.