Solving Matching Problems Efficiently in Bipartite Graphs

摘要: We investigate the problem maxDMM of computing a largest set pairwise disjoint maximum matchings in undirected graphs. In this paper, n, m denote, respectively, number vertices and edges. solve for bipartite graphs, by providing an \(O(n^{1.5}\sqrt{m/\log n} + mn\log n)\)-time algorithm. design better algorithms complete bisplit (Bisplit graphs are with nested neighborhood property.) Specifically, we prove that is solvable time O(m). A sequence \(S=(s_1,\cdots ,s_t)\) positive integers said to be color-feasible graph G, if there exists proper edge-coloring G colors \(1,\cdots ,t\), such precisely \(s_i\) edges have color i, every \(i=1,\cdots ,t\). Actually, that, any S which corresponding can obtained For (1) \(O(mn\log n)\), (2) \(O(n^2\log algorithm count all matchings. This latter same runs best known [17], but our much simpler than one given [17]. The key idea underlying both results O(n)-time enumeration their minimal vertex covers.