新论文 · v1arXiv:2610.40591
最大基数匹配的 n^{2+o(1)} 时间算法
Maximum Cardinality Matching in $n^{2+o(1)}$ Time
George Z. Li, Jason Li, Junkai Zhang
AI 速览：作者提出一个在一般图上以 n^{2+o(1)} 时间求解最大基数匹配的算法，思路是扩展近期组合最大流技术到斜对称流问题。
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.
cs.DS