Finding all maximally-matchable edges in a bipartite graph

DOI10.1016/J.TCS.2011.12.071zbMATH Open1241.05117DBLPjournals/tcs/Tassa12OpenAlexW1998124720WikidataQ56341084 ScholiaQ56341084MaRDI QIDQ418005FDOQ418005

Authors Tamir Tassa

Publication date 14 May 2012

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

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

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)

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.

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

Cites work

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

Cited in

(17)

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

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)