OVERVIEW OF GRAPH PARTITIONING WITH NATURAL HEURISTICS CUTS

[摘要] This paper will present a short overview of several approaches to solve the k-way graph partitioning problem. In short this problem considers the partitioning of a graph in k partitions, in such a way that one minimizes the cut value. The cut value represents the number of edges crossing this partitions.The technique for simultaneous segmentation and classification of image partitions using graph cuts. By combining existing image segmentation approaches with simple learning techniques. We manage to include prior knowledge into this visual grouping process.

[关键词] graph partitioning;road networks;minimum cuts;maximum flows;algorithms, image segmentation