A simple reduction from maximum weight matching to maximum cardinality matching

被引:11
作者
Pettie, S. [1 ]
机构
[1] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA
基金
美国国家科学基金会;
关键词
Graph algorithms; Maximum matching; FASTER SCALING ALGORITHMS; GRAPHS; PATHS;
D O I
10.1016/j.ipl.2012.08.010
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Let MCM(m, n) and MWM(m. n. N) be the complexities of computing a maximum cardinality matching and a maximum weight matching, and let MCMbi, MWMbi be their counterparts for bipartite graphs, where m, n, and N are the edge count, vertex count, and maximum integer edge weight. Kao, Lam, Sung, and Ting (2001) [1] gave a general reduction showing MWMbi(m, n, N) = 0(N . MCMbi(m, n)) and Huang and Kavitha (2012) [2] recently proved the analogous result for general graphs, that MWM(m. n, N) = 0(N . MCM(m,n)). We show that Gabow's MWMbi and MWM algorithms from 1983 [3] and 1985 [4] can be modified to replicate the results of Kao et al. and Huang and Kavitha, but with dramatically simpler proofs. We also show that our reduction leads to new bounds on the complexity of MWM on sparse graph classes, e.g., (bipartite) planar graphs, bounded genus graphs, and H-minor-free graphs. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:893 / 898
页数:6
相关论文
共 32 条
  • [1] [Anonymous], ARXIV11120790
  • [2] [Anonymous], 2002, Proceedings of the 34th annual ACM symposium on theory of computing, STOC' 02
  • [3] [Anonymous], 1970, Soviet Math. Doklady
  • [4] [Anonymous], 2012, P 23 ANN ACM SIAM S
  • [5] [Anonymous], J ACM
  • [6] Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
    Borradaile, Glencora
    Klein, Philip N.
    Mozes, Shay
    Nussbaum, Yahav
    Wulff-Nilsen, Christian
    [J]. 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 170 - 179
  • [7] Cheriyan J, 1996, ALGORITHMICA, V15, P521, DOI 10.1007/BF01940880
  • [8] Duan R., 2012, P 23 ANN ACM SIAM S, P1413, DOI DOI 10.1137/1.9781611973099.111
  • [9] PATHS TREES AND FLOWERS
    EDMONDS, J
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03): : 449 - &
  • [10] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES
    EDMONDS, J
    [J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 125 - +