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 条
  • [21] An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph
    Borradaile, Glencora
    Klein, Philip
    JOURNAL OF THE ACM, 2009, 56 (02)
  • [22] An O(n log n) algorithm for maximum st-flow in a directed planar graph
    Borradaile, Glencora
    Klein, Philip
    PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 524 - 533
  • [23] AN O(N) TIME ALGORITHM FOR MAXIMUM MATCHING ON COGRAPHS
    YU, MS
    YANG, CH
    INFORMATION PROCESSING LETTERS, 1993, 47 (02) : 89 - 93
  • [24] Computing the shortest watchtower of a polyhedral terrain in O(n log n) time
    Zhu, BH
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 8 (04): : 181 - 193
  • [25] Computing Smallest and Largest Repetition Factorizations in O(n log n) Time
    Inoue, Hiroe
    Matsuoka, Yoshiaki
    Nakashima, Yuto
    Inenaga, Shunsuke
    Bannai, Hideo
    Takeda, Masayuki
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2016, 2016, : 135 - 145
  • [26] Constructing a cactus for minimum cuts of a graph in O (mn+n2 log n) time and O(m) Space
    Nagamochi, H
    Nakamura, S
    Ishii, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (02): : 179 - 185
  • [27] Bisimilarity Minimization in O(m log n) Time
    Valmari, Antti
    APPLICATIONS AND THEORY OF PETRI NETS, PROCEEDINGS, 2009, 5606 : 123 - 142
  • [28] Perfect Matchings in O (n1.5) Time in Regular Bipartite Graphs
    Goel, Ashish
    Kapralov, Michael
    Khanna, Sanjeev
    COMBINATORICA, 2019, 39 (02) : 323 - 354
  • [29] Computing the quartet distance between evolutionary trees in time O(n log n)
    Brodal, GS
    Fagerberg, R
    Pedersen, CNS
    ALGORITHMICA, 2004, 38 (02) : 377 - 395
  • [30] Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)
    Gerth Stølting Brodal
    Rolf Fagerberg
    Christian N.S. Pedersen
    Algorithmica , 2004, 38 : 377 - 395
12345