Finding all maximally-matchable edges in a bipartite graph
From MaRDI portal
Publication:418005
DOI10.1016/j.tcs.2011.12.071zbMath1241.05117arXiv1107.4711WikidataQ56341084 ScholiaQ56341084MaRDI QIDQ418005
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
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