Finding all maximally-matchable edges in a bipartite graph

DOI10.1016/j.tcs.2011.12.071zbMath1241.05117arXiv1107.4711WikidataQ56341084 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 graphs; perfect matchings; maximally-matchable edges; maximum matchings

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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