### Implementation of $\textit{O}(\textit{nm}log\textit{n})$ weighted matchings in general graphs: the power of data structuresImplementation of $\textit{O}(\textit{nm}log\textit{n})$ weighted matchings in general graphs: the power of data structures

Access Restriction
Subscribed

 Author Mehlhorn, Kurt ♦ Schfer, Guido Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2002 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Abstract We describe the implementation of an algorithm which solves the weighted matching problem in general graphs with $\textit{n}$ vertices and $\textit{m}$ edges in time O(nm log n). Our algorithm is a variant of the algorithm of Galil, Micali and Gabow [Galil et al. 1986] and extensively uses sophisticated data structures, in particular concatenable priority queues, so as to reduce the time needed to perform dual adjustments and to find tight edges in Edmonds' blossom-shrinking algorithm.We compare our implementation to the experimentally fastest implementation, named Blossom IV, due to Cook and Rohe [Cook and Rohe 1997]. Blossom IV requires only very simple data structures and has an asymptotic running time of $O(n^{2}m).$ Our experiments show that our new implementation is superior to Blossom IV. A closer inspection reveals that the running time of Edmonds' blossom-shrinking algorithm in practice heavily depends on the time spent to perform dual adjustments and to find tight edges. Therefore, optimizing these operations, as is done in our implementation, indeed speeds-up the practical performance of implementations of Edmonds' algorithm. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2002-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 7 Starting Page 4

#### Open content in new tab

Source: ACM Digital Library