Rank-Maximal Matchings

leda::list<leda::edge> BI_RANK_MAX_MATCHING(leda::graph& G, leda::edge_array<int> rank)

G is a simple, loopfree, bipartite graph and rank is a positive integer function on the edges of G. The function computes a Rank-Maximal matching M of G, that is a matching which uses the largest possible number of rank one edges, and subject to this constraint the largest possible number of rank two edges and so on.
The matching is returned as a list of edges.
The running time is O(C $\sqrt{{n}}$ m) where C is the maximum rank of an edge used in the matching.
Precondition G is simple, loopfree and bipartite
Precondition rank is positive

leda::list<leda::edge> BI_RANK_MAX_MATCHING_MWMR(leda::graph& G, leda::edge_array<int> rank)

G is a simple, loopfree, bipartite graph and rank is a positive integer function on the edges of G. The function computes a Rank-Maximal matching M of G, that is a matching which uses the largest possible number of rank one edges, and subject to this the largest possible number of rank two edges and so on.
The matching is returned as a list of edges.
This procedure solves the problem by reducing it to the maximum weight matching problem, and therefore the running time is O(n²(m + n log n)). The second n comes from the possibly large cost of arithmetic since the reduction involves edge weights which can be as large as nⁿ. The space requirement is O(n²).
Precondition G is simple, loopfree and bipartite
Precondition rank is positive

leda::array<int> BI_RANK_MAX_MATCHING_PROFILE(leda::graph G, leda::edge_array<int> rank, leda::list<leda::edge> matching)

G is a graph and rank is a positive integer function on the edges of G. matching is a list of edges belonging to the matching. The function returns an array ar of non-negative integers representing the number of edges of each rank belonging to the matching. This array is indexed from 1 to n, where n is the number of vertices of G.
The running time is O(n) where n is the number of nodes of G.
Note that this procedure does not check whether the list of edges is really a matching or not.
Precondition rank is positive

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

The command line arguments were:
latex2html -split 0 -local_icons -html_version 3.2,math -no_math RANK_MAX_MATCHING.tex

The translation was initiated by Dimitris Michail on 2004-10-20

Dimitris Michail 2004-10-20

leda::list<leda::edge>	BI_RANK_MAX_MATCHING(leda::graph& G, leda::edge_array<int> rank)
		G is a simple, loopfree, bipartite graph and rank is a positive integer function on the edges of G. The function computes a Rank-Maximal matching M of G, that is a matching which uses the largest possible number of rank one edges, and subject to this constraint the largest possible number of rank two edges and so on. The matching is returned as a list of edges. The running time is O(C $\sqrt{{n}}$ m) where C is the maximum rank of an edge used in the matching. Precondition G is simple, loopfree and bipartite Precondition rank is positive
leda::list<leda::edge>	BI_RANK_MAX_MATCHING_MWMR(leda::graph& G, leda::edge_array<int> rank)
		G is a simple, loopfree, bipartite graph and rank is a positive integer function on the edges of G. The function computes a Rank-Maximal matching M of G, that is a matching which uses the largest possible number of rank one edges, and subject to this the largest possible number of rank two edges and so on. The matching is returned as a list of edges. This procedure solves the problem by reducing it to the maximum weight matching problem, and therefore the running time is O(n²(m + n log n)). The second n comes from the possibly large cost of arithmetic since the reduction involves edge weights which can be as large as nⁿ. The space requirement is O(n²). Precondition G is simple, loopfree and bipartite Precondition rank is positive
leda::array<int>	BI_RANK_MAX_MATCHING_PROFILE(leda::graph G, leda::edge_array<int> rank, leda::list<leda::edge> matching)
		G is a graph and rank is a positive integer function on the edges of G. matching is a list of edges belonging to the matching. The function returns an array ar of non-negative integers representing the number of edges of each rank belonging to the matching. This array is indexed from 1 to n, where n is the number of vertices of G. The running time is O(n) where n is the number of nodes of G. Note that this procedure does not check whether the list of edges is really a matching or not. Precondition rank is positive