Two Algorithms for Bipartite Graphs
Two Algorithms for Bipartite Graphs
复制标题
二分图的两种算法
DOI：
10.1137/0111014
复制
发表时间：
1963
期刊：
影响因子：
--
通讯作者：
N. S. Mendelsohn
中科院分区：
文献类型：
--
作者：
A. Dulmage;N. S. Mendelsohn
1. 简介。 Marshall Hall [6] 给出了一种算法，用于在子集集合存在时找到具有不同代表的系统。在本文中，该算法被扩展以查找矩阵的秩[3, 9]，并提供一种确定相应最大横截面的方法。这个算法将被称为横向算法。作者[2]给出了一个算法来确定 nn X n 二部图是否是不可约的。在本文中，该算法被扩展以提供确定 m X n 二分图的完全规范分解的方法。该算法将剔除分解算法。
1. Introduction. Marshall Hall [6] has given an algorithm for finding a system of distinct representatives for a collection of subsets whenever such a system exists. In this paper, this algorithm is extended to find the term rank [3, 9] of a matrix and to provide a method of determining the corresponding maximum transversal. This algorithm will be called the transversal algorithm.The authors [2] have given an algorithm for determining whether or not nn X n bipartitegraph is irreducible. In this paper this algorithm is extended to provide method for determining the complete canonical decomposition of an m X n bipartite graph. This algorithm will be culled the decomposition ulgorithm.