Solve for Maximum Cardinality Matching

Finds the maximum cardinality matching in graphs and bipartite graphs.

Usage

MaxCardinalityMatching(
  arcSources,
  arcTargets,
  numNodes,
  algorithm = "MaxMatching"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

numNodes

The number of nodes in the graph

algorithm

Choices of algorithm include "MaxMatching" and "MaxFractionalMatching". "MaxMatching" is the default.

Value

A named list containing two entries: 1) "value": the matching value, 2) "edges": the edges of the final graph, in a List of (node, node) pairs

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00615.html.