论文部分内容阅读
本文介绍简单连通图着色问题的一个近似算法,就是借助于图的一个最小支配集,将图划分成若干个子图,分别对这些子图着色,再合并起来,便得到整个问题的解。着重介绍了应用代数运算寻找图的一个最小支配集的算法。此外,本文还论证了该近似算法的渐近时间复杂性是 O(n~3)。
In this paper, we introduce an approximate algorithm of simple connected graph coloring problem, which is to divide the graph into several subgraphs by means of a minimal dominant set of graphs. Color the subgraphs separately and then combine to get the solution of the whole problem. The algorithm of algebraic arithmetic to find a minimal dominant set of graphs is emphatically introduced. In addition, the paper also demonstrates that the asymptotic time complexity of this approximation algorithm is O (n ~ 3).