V
 the graph vertex typeE
 the graph edge typepublic class GreedyMaximumCardinalityMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
Independent of the mode, the resulting matching is maximal, and is therefore guaranteed to contain at least half of the edges that a maximum cardinality matching has ($\frac{1}{2}$ approximation). Runtime complexity: $O(m)$ when the edges are not sorted, $O(m + m \log n)$ otherwise, where $n$ is the number of vertices, and $m$ the number of edges.
MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>
DEFAULT_EPSILON
Constructor and Description 

GreedyMaximumCardinalityMatching(Graph<V,E> graph,
boolean sort)
Creates a new GreedyMaximumCardinalityMatching instance.

Modifier and Type  Method and Description 

MatchingAlgorithm.Matching<V,E> 
getMatching()
Get a matching that is a $\frac{1}{2}$approximation of the maximum cardinality matching.

public MatchingAlgorithm.Matching<V,E> getMatching()
getMatching
in interface MatchingAlgorithm<V,E>
Copyright © 2019. All rights reserved.