平面图4-割问题的O(|V|~2)算法

AN O(|V|~2)ALGORITHM FOR THE PLANAR 4-CUT PROBLEM

<正> 给定一个简单图 G=(V,E).V 是顶点集,E■V×V 是边集.所谓 k-割乃是E 的一个子集 E_1,它使图 G_1=(V,E—E_1)恰包含 k 个分支.寻找一个图的最小 k-割问题,无论在理论上和实践中都有重要的意义.Hochbaum 和 shmoys 在文献[1]中给出了平面图最小3-割的 O(|V|~2)算法.本文将给出一个平面图最小4-割的O(|V|~2)算法.本文用到的概念及符号记法均与文献[1]一致.

A 4-cut for a connected graph G is a set of edges which,When deleted,separate G into 4components.In this paper an O(|V|~2) algorithm for finding the minimum 4-cut for a planargraph G is presented.