COMPUTING A MAXIMUM CARDINALITY MATCHING IN A BIPARTITE GRAPH IN TIME O(N1.5-SQUARE-ROOT-M/LOG N)

被引：80

作者：

ALT, H

BLUM, N

MEHLHORN, K

PAUL, M

机构：

[1] UNIV BONN,W-5300 BONN,GERMANY

[2] UNIV SAARLAND,FACHBEREICH INFORMAT,W-6600 SAARBRUCKEN,GERMANY

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 37卷 / 04期

关键词：

ANALYSIS OF ALGORITHMS; BIPARTITE GRAPH; MATCHING;

D O I：

10.1016/0020-0190(91)90195-N

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show how to compute a maximum cardinality matching in a bipartite graph of n vertices in time O(n1.5 square-root m/log n). For dense graphs this improves on the O(square-root n m) algorithm of Hopcroft and Karp. The speed-up is obtained by an application of the fast adjacency matrix scanning technique of Cheriyan, Hagerup and Mehlhorn.

引用

页码：237 / 240

页数：4