图的最优K划分

THE OPTIMAL K-PARTITIONING OF GRAPHS

本文提出了一种新型的最优K划分算法,此算法借助一有效的启发式估价函数,将划分问题转换为状态空间最小耗散路径的搜索问题,再利用A算法给出最优K划分算法。

A new K-partitioning method for graphs is presented. With the help of an efficient heuristic evaluation function, this method transforms K-partitioning problem into search problem in state-space, and then solves it with A* algorithm.