Overview

Given a graph G=(V,E), a matching M is set of edges without common vertices, i.e. the graph G=(V,M) has degree of at most one. The Global Paths Algorithm (GPA), was proposed by Maue and Sanders in "Engineering Algorithms for Approximate Weighted Matching" (WEA'07) as a synthesis of Greedy and Path Growing algorithms by Drake et. al. The greedy algorithm sorts the edges by descending weight (or rating) and then scans them. If an edge {u,v} and its end points are not matched yet, it is put into the matching.

Similar to the Greedy approach, GPA scans the edges in order of decreasing weight (or rating); but rather than immediately building a matching, it first constructs a collection of paths and even length cycles. To be more precise, these paths initially contain no edges. While scanning the edges, the set is extended by successively adding applicable edges. An edge is called applicable if it connects two endpoints of different paths or the two endpoints of an odd length path. Afterwards, optimal solutions/matchings are computed for each of these paths and cycles using dynamic programming. Both algorithms achieve a half-approximation in the worst case, but empirically, GPA gives considerably better results.

This is our implementation of the global paths matching algorithm. The algorithm has been originally used withing the graph partitioning framework KaHIP. We hope that the implementation of the algorithm will be of independant use.

Licence

The program is licenced under GPL 3.0. If you publish results using our algorithms, please acknowledge our work by quoting the following paper:

@inproceedings{kaffpa,
             author = {P. Sanders and C. Schulz},
             title = {{Engineering Multilevel Graph Partitioning Algorithms}},
             booktitle = {Proceedings of the 19th European Symposium on Algorithms},
             year = {2011},
             pages = {469--480},
             publisher = {Springer},
             series = {LNCS},
             volume = {6942},
             isbn = {978-3-642-23718-8}
}

Download

Support

  • Write us an email if you need support!