Projects / Global Paths Matching

Global Paths Matching

Global Paths Matching is an implementation of the global paths graph matching algorithm proposed by Maue and Sanders in "Engineering Algorithms for Approximate Weighted Matching" (WEA'07). Given a graph G=(V,E), a matching M is a set of edges without common vertices, i.e. the graph G=(V,M) has a degree of at most one. The algorithm scans the edges in order of decreasing weight (or rating), constructing a collection of paths and even length cycles. These paths initially contain no edges. While scanning the edges, the set is extended by successively adding applicable edges, which are those connecting two endpoints of different paths or two endpoints of an odd length path. Optimal solutions/matchings are computed for each path and cycle using dynamic programming.

Tags
Licenses
Operating Systems

Recent releases

  •  10 Jan 2014 10:38

    Release Notes: This is the initial release of the software.

    Screenshot

    Project Spotlight

    OpenStack4j

    A Fluent OpenStack client API for Java.

    Screenshot

    Project Spotlight

    TurnKey TWiki Appliance

    A TWiki appliance that is easy to use and lightweight.