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

被引：79
|
作者：
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
相关论文
共 50 条
  • [1] AN O(N LOG N LOG LOG N) PARALLEL MAXIMUM MATCHING ALGORITHM FOR BIPARTITE GRAPHS
    KIM, T
    CHWA, KY
    INFORMATION PROCESSING LETTERS, 1987, 24 (01) : 15 - 17
  • [2] COMPUTING THE GIRTH OF A PLANAR GRAPH IN O(n log n) TIME
    Weimann, Oren
    Yuster, Raphael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (02) : 609 - 616
  • [3] Computing the Girth of a Planar Graph in O (n log n) Time
    Weimann, Oren
    Yuster, Raphael
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2009, 5555 : 764 - +
  • [4] Maximum Cardinality f-Matching in Time O(n2/3m)
    Gabow, Harold n.
    ACM TRANSACTIONS ON ALGORITHMS, 2025, 21 (01)
  • [5] An O(n log log n) time algorithm for constructing a graph of maximum connectivity with prescribed degrees
    Asano, T
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 51 (03) : 503 - 510
  • [6] Matching nuts and bolts in O(n log n) time
    Komlos, J
    Ma, Y
    Szemeredi, E
    PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 232 - 241
  • [7] Matching nuts and bolts in O(n log n) time
    Komlos, J
    Ma, Y
    Szemeredi, E
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (03) : 347 - 372
  • [8] An O(n(log n)3) algorithm for maximum matching in trapezoid graphs
    Ngoc-Khang Le
    Phan-Thuan Do
    PROCEEDINGS OF 2013 IEEE RIVF INTERNATIONAL CONFERENCE ON COMPUTING AND COMMUNICATION TECHNOLOGIES: RESEARCH, INNOVATION, AND VISION FOR THE FUTURE (RIVF), 2013, : 157 - 162
  • [9] Finding a maximum matching in a sparse random graph in O(n) expected time
    Chebolu, Prasad
    Frieze, Alan
    Melsted, Pall
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 2008, 5125 : 161 - 172
  • [10] Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
    Chebolu, Prasad
    Frieze, Alan
    Melsted, Pall
    JOURNAL OF THE ACM, 2010, 57 (04)
12345