Efficient algorithms for finding maximum matching in graphs

By Zvi Galil. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Quantifying the benefits of vehicle pooling with shareability networks (2013, methodology): “For instance, we can use Edmond’s algorithm for weighted matching [11] , which on a sparse graph yields time complexity O(n(2) log n).”
SimAlign: High Quality Word Alignments without Parallel Training Data using Static and Contextualized Embeddings (2020, unknown): “, (Galil, 1986)).”
An exact distribution‐free test comparing two multivariate distributions based on adjacency (2005, unknown): “See Galil (1986) for a survey and see Papadimitriou and Steiglitz (1982), section 11.3, for one text-book discussion.”
The Amborella Genome and the Evolution of Flowering Plants (2013, methodology): “A comprehensive analysis of Amborella and the three subgenomes from the representative rosids (combining a number of computational techniques) ( 29 , 31 , 32 ) enabled a completely automated reconstruction of ancestral gene order beyond the level of “ contiguous ancestral regions ” [compare ( 33 )].”
A similarity measure for analyzing human activities using human-object interaction context (2014, background): “hard problem, while the best known exact algorithm for solving the maximum weight matching is O(n(3)), where n is the number node (visual mini-bags) in the graph [17].”
Automated assembly scaffolding using RagTag elevates a new tomato system for high-throughput genome editing (2022, unknown): “To find a solution to this graph and output a patched assembly, a maximal weight matching is computed with networkx and if there are any cycles, they are broken [33].”
Automated assembly scaffolding elevates a new tomato system for high-throughput genome editing (2021, unknown): “To find a solution to this graph and output a patched assembly, a maximal weight matching is computed with networkx and if there are any cycles, they are broken [27].”
Valence Bonds in Random Quantum Magnets: Theory and Application to YbMgGaO4 (2017, methodology): “We computed the complete dimer covering with minimum dimer energy using the famous blossom algorithm of Edmond [171,172] as implemented in the NetworkX PYTHON package (implementation by van Rantwijk, “max_weight_matching”with “maxcardinality 1⁄4 True”; weights are interpreted as negative energies).”
Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks (2011, background): “For instance, although graph matching is in general NP-complete, there ismuch active research in speeding up matching on the average or in special cases (Gold &Rangarajan, 1996; Galil, 1986).”
Mix zones: user privacy in location-aware services (2004, background): “a weighted bipartite graph has several polynomial time algorithms [ 5 ].”
The Algorithm Design Manual (2020, unknown): “Survey articles on matching algorithms include [Gal86].”