MaxCardinalityMatching {rlemon}

Solve for Maximum Cardinality Matching

Description

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.

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.

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