Maximum matching found faster in general graphs with new algorithm
Maximum Cardinality Matching in $n^{2+o(1)}$ Time
Data Structures and Algorithms
Summary
Finding the largest matching in a network of connections is an important problem in computer science. This paper introduces a new method that solves this problem faster than before for general graphs. The authors build on recent improvements in flow algorithms and extend them to work with a broader type of network flow that covers matchings. Their approach leads to better performance when handling large and complex networks.
What this means in practice
- •For network engineers: Improve resource allocation in communication networks by quickly finding optimal pairings between nodes.
- •For operations researchers: Speed up solutions to matching problems in logistics and scheduling that involve complex network structures.
Authors
George Z. Li, Jason Li, Junkai Zhang
Abstract
We consider the maximum cardinality matching problem in general graphs, and give an $n^{2+o(1)}$-time algorithm for the problem. Our work builds on recent work on combinatorial algorithms for maximum flow and extends the techniques to skew-symmetric flow problems which capture general matchings as a special case.