| 求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法 |
| |
| 引用本文： | 洪大威. 求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法[J]. 上海师范大学学报(自然科学版), 1987, 0(3) |
| |
| 作者姓名： | 洪大威 |
| |
| 作者单位： | 华东师范大学计算机系 |
| |
| 摘 要： | 本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G))|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集
|
| 关 键 词： | 二分图的最小复盖 0-1矩阵的线秩 作用在集上的群 |
An Efficient Algorithm for Determining the Intersection of All Minimal Coverings in Bipartite Graph |
| |
| HONG DAWEI. An Efficient Algorithm for Determining the Intersection of All Minimal Coverings in Bipartite Graph[J]. Journal of Shanghai Normal University(Natural Sciences), 1987, 0(3) |
| |
| Authors: | HONG DAWEI |
| |
| Affiliation: | Computer Science Department |
| |
| Abstract: | |
| |
| Keywords: | the minimal covering in a bipartite graph the line rank of a 0-1 matrix the group acting on a set |
| 本文献已被 CNKI 等数据库收录！ |
