An $O(N \cdot \log N)$ Algorithm for a Class of Matching Problems
Nimrod Megiddo, Arie Tamir · SIAM Journal on Computing · 1978
The following class of matching problems is considered. The vertices of a complete undirected graph are indexed $1, \cdots ,n$, where $n = 2m$. Every vertex i is assigned two numbers $a_i $, $b_i $. The length of every edge $(i,j)$, where $i < j$, is $d(i,j) = a_i + b_j $. This class of weighted graphs is applicable to scheduling and optimal assignment problems. A maximum weighted (perfect) matching is found in $O(n \cdot \log n)$ operations.