| 平面图 4-割问题的 O(|V|~2)算法 |
| |
| 引用本文： | 赵连昌.平面图 4-割问题的 O(|V|~2)算法[J].系统科学与数学,1990,10(1):040-045. |
| |
| 作者姓名： | 赵连昌 |
| |
| 作者单位： | 东北工学院，沈阳黄金学院 沈阳 |
| |
| 摘 要： | 给定一个简单图 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]一致.
|
AN O(|V|~2)ALGORITHM FOR THE PLANAR 4-CUT PROBLEM |
| |
| ZHAO LIAN-CHANG,LOU HUI-YUAN.AN O(|V|~2)ALGORITHM FOR THE PLANAR 4-CUT PROBLEM[J].Journal of Systems Science and Mathematical Sciences,1990,10(1):040-045. |
| |
| Authors: | ZHAO LIAN-CHANG LOU HUI-YUAN |
| |
| Institution: | (1)Northeast Institute of Technology,Shenyang;(2)Shenyang Gold College,Shenyang |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
