CAJ | 학술논문

针对各类图论着色频谱分配算法的时间开销过大的问题，提出了一种并行单色连通分支处理拓扑图的方法。该方法结合连通分量理论和单色子图分解法，可应用于目前所有的图论着色模型的拓扑图分解中。并且根据认知用户的需求来调整分配使满意的用户比例增大，从而解决了分配结果存在的用户满意度不均衡情况。仿真结果表明，提出的算法是一种快速且能够使更多用户满足需求的有效方法。
침대각류도론착색빈보분배산법적시간개소과대적문제，제출료일충병행단색련통분지처리탁복도적방법。해방법결합련통분량이론화단색자도분해법，가응용우목전소유적도론착색모형적탁복도분해중。병차근거인지용호적수구래조정분배사만의적용호비례증대，종이해결료분배결과존재적용호만의도불균형정황。방진결과표명，제출적산법시일충쾌속차능구사경다용호만족수구적유효방법。
This paper analyzes the various spectrum allocation algorithms of graph coloring theory and concerns the problem of costing too much time. It combines connected component theory with the method that divides graph into subgraphs which have one color. A new method is proposed, which can parallel process all one-colored connected branches. This method can be applied to each algorithm to divide graph into small slices. And in view of the problem of unbalanced degree of users’ satisfaction, an amendment is presented, which adjusts allocated spectrums to improve the proportion of satisfied users. The simulation results show that the proposed algorithm is fast and makes more users meet the needs of requirements effectively.