Treffer: Implementation of O(nmlog n) Weighted Matchings in General Graphs. The Power of Data Structures.
Title:
Implementation of O(nmlog n) Weighted Matchings in General Graphs. The Power of Data Structures.
Authors:
Goos, Gerhard1, Hartmanis, Juris2, van Leeuwen, Jan3, Näher, Stefan4 naeher@informatik.uni-trier.de, Wagner, Dorothea5 Dorothea.Wagner@uni-konstanz.de, Mehlhorn, Kurt6 mehlhorn@mpi-sb.mpg.de, Schäfer, Guido6 schaefer@mpi-sb.mpg.de
Source:
Algorithm Engineering. 2001, p23-38. 16p.
Database:
Supplemental Index
Weitere Informationen
We describe the implementation of an O(nmlog n) algorithm for weighted matchings in general graphs. The algorithm is a variant of the algorithm of Galil, Micali, and Gabow [12] and requires the use of concatenable priority queues. No previous implementation had a worst-case guarantee of O(nmlog n). We compare our implementation to the experimentally fastest implementation (called Blossom IV) due to Cook and Rohe [4]; Blossom IV is an implementation of Edmonds' algorithm and has a running time no better than (n3). Blossom IV requires only very simple data structures. Our experiments show that our new implementation is competitive to Blossom IV. [ABSTRACT FROM AUTHOR]