To Do

  1. Comprehensive improvements to the implementation:

    • Extended doctests covering:

      • best-case scenarios,

      • worst-case time complexity examples, and

      • examples for each method of the class.

    • Method to collect and report algorithm execution statistics, including:

      • number of blossoms formed,

      • number of augmenting paths found,

      • number of phases executed,

      • time spent in each phase, etc.

    • Parallel processing wherever possible to speed up computation, for example:

      • processing multiple augmenting paths simultaneously, and

      • computing the matching for each connected components of the graph concurrently.

    • Performance and complexity improvements:

      • Use a specialized disjoint set union variant to reduce the time to find the \(k\)-th bud/base of a vertex to \(\mathcal{O}(\alpha(m, n))\) on RAM models [1],

      • Explore and implement further heuristics to optimize the algorithm in practice.

  2. Documentation and comments:

    • Write detailed comments and documentation for the implementation

    • Provide clear interfaces for:

      • statistics collection,

      • parallel execution features,

      • authors and references, and

      • clear comments using the statements from the original paper [2], [3].

References