Finding all maximally-matchable edges in a bipartite graph

DOI10.1016/J.TCS.2011.12.071zbMATH Open1241.05117DBLPjournals/tcs/Tassa12arXiv1107.4711OpenAlexW1998124720WikidataQ56341084 ScholiaQ56341084MaRDI QIDQ418005FDOQ418005

Authors: Tamir Tassa 

Publication date: 14 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of finding all allowed edges in a bipartite graph $G=(V,E)$, i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time $O(n+m)$ (where $n=|V|$ and $m=|E|$). Hence, the time complexity of finding all allowed edges reduces to that of finding a single maximum matching, which is $O(n^{1/2}m)$ [Hopcroft and Karp 1973], or $O((n/logn{)}^{1/2}m)$ for dense graphs with $m=Theta(n^2)$ [Alt et al. 1991]. This time complexity improves upon that of the best known algorithms for the problem, which is $O(nm)$ ([Costa 1994] for bipartite graphs, and [Carvalho and Cheriyan 2005] for general graphs). Other algorithms for solving that problem are randomized algorithms due to [Rabin and Vazirani 1989] and [Cheriyan 1997], the runtime of which is $ildeO(n^{2.376})$. Our algorithm, apart from being deterministic, improves upon that time complexity for bipartite graphs when $m=O(n^r)$ and $r<1.876$. In addition, our algorithm is elementary, conceptually simple, and easy to implement.

Full work available at URL: https://arxiv.org/abs/1107.4711

Recommendations

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• scientific article; zbMATH DE number 177842
• A fast dynamic optimum algorithm for maximum matching in bipartite graphs
• Finding maximum matching for bipartite graphs in parallel

zbMATH Keywords

perfect matchingsbipartite graphsmaximally-matchable edgesmaximum matchings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• Depth-First Search and Linear Graph Algorithms
• The complexity of computing the permanent
• Finding all the perfect matchings in bipartite graphs
• Persistency in maximum cardinality bipartite matchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• On Representatives of Subsets
• Database Theory - ICDT 2005
• Algorithms for dense graphs and networks on the random access computer
• Perfect matchings in \(O(n \log n)\) time in regular bipartite graphs
• An \(O(VE)\) algorithm for ear decompositions of matching-covered graphs
• Maximum matchings in general graphs through randomization
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory

Cited In (17)

• Optimum matchings in weighted bipartite graphs
• Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
• Recomputing causality assignments on lumped process models when adding new simplification assumptions
• Reconstruction of domino tilings -- combinatorial and probabilistic questions
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Efficiently-verifiable strong uniquely solvable puzzles and matrix multiplication
• Finding a maximum matching in a permutation graph
• Permanents, \(\alpha\)-permanents and Sinkhorn balancing
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• A fast dynamic optimum algorithm for maximum matching in bipartite graphs
• The graphs of stably matchable pairs
• Finding maximum edge bicliques in convex bipartite graphs
• Generic pole assignability, structurally constrained controllers and unimodular completion
• Computing asymmetric median tree of two trees via better bipartite matching algorithm
• Addendum to ``Finding all maximally-matchable edges in a bipartite graph
• Title not available (Why is that?)
• Privacy by diversity in sequential releases of databases

This page was built for publication: Finding all maximally-matchable edges in a bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418005)