Finding all maximally-matchable edges in a bipartite graph

DOI10.1016/j.tcs.2011.12.071zbMath1241.05117arXiv1107.4711OpenAlexW1998124720WikidataQ56341084 ScholiaQ56341084MaRDI QIDQ418005

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

bipartite graphsperfect matchingsmaximally-matchable edgesmaximum matchings

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Optimum matchings in weighted bipartite graphs ⋮ Addendum to ``Finding all maximally-matchable edges in a bipartite graph ⋮ The graphs of stably matchable pairs ⋮ Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ Reconstruction of domino tilings -- combinatorial and probabilistic questions ⋮ Generic pole assignability, structurally constrained controllers and unimodular completion ⋮ Privacy by diversity in sequential releases of databases ⋮ Permanents, \(\alpha\)-permanents and Sinkhorn balancing ⋮ Recomputing causality assignments on lumped process models when adding new simplification assumptions

Cites Work

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

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