V- the graph vertex type
E- the graph edge type
public class MaximumWeightBipartiteMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
Running time is $O(n(m+n \log n))$ where n is the number of vertices and m the number of edges of the input graph. Uses exact arithmetic and produces a certificate of optimality in the form of a tight vertex potential function.
This is the algorithm and implementation described in the LEDA book. See the LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999.
|Constructor and Description|
|Modifier and Type||Method and Description|
Compute a matching for a given graph.
Get the weight of the matching.
Get the vertex potentials.
graph- the input graph
partition1- the first partition of the vertex set
partition2- the second partition of the vertex set
IllegalArgumentException- if the graph is not undirected
public MatchingAlgorithm.Matching<V,E> getMatching()
public Map<V,BigDecimal> getPotentials()
This is a tight non-negative potential function which proves the optimality of the maximum weight matching. See any standard textbook about linear programming duality.
public BigDecimal getMatchingWeight()
Copyright © 2018. All rights reserved.