Functions
leda::list< leda::edge >	mosp::BI_RANK_MAX_MATCHING (leda::graph &G, const leda::edge_array< int > &rank)
	Compute a rank-maximal matching of a bipartite graph. More...

leda::list< leda::edge >	mosp::BI_RANK_MAX_MATCHING_MWMR (leda::graph &G, const leda::edge_array< int > &rank)
	Compute a rank-maximal matching of a bipartite graph. More...

leda::list< leda::edge >	mosp::DBI_RANK_MAX_MATCHING_MWMR (leda::graph &G, const leda::edge_array< int > &rank)
	Compute a rank-maximal matching of a bipartite graph. More...

leda::array< int >	mosp::BI_RANK_MAX_MATCHING_PROFILE (const leda::graph &G, const leda::edge_array< int > &rank, const leda::list< leda::edge > &matching)
	Compute the profile of a matching. More...

leda::list< leda::edge >	mosp::BI_RANK_MAX_CAPACITATED_MATCHING (const leda::graph &G, const leda::list< leda::node > &A, const leda::list< leda::node > &B, const leda::node_array< int > &capacity, const leda::edge_array< int > &rank)
	Compute a rank-maximal matching of a bipartite graph with capacities on the right side of the bipartite graph. More...

Detailed Description

Function Documentation

leda::list<leda::edge> mosp::BI_RANK_MAX_CAPACITATED_MATCHING	(	const leda::graph &	G,
		const leda::list< leda::node > &	A,
		const leda::list< leda::node > &	B,
		const leda::node_array< int > &	capacity,
		const leda::edge_array< int > &	rank
	)

Compute a rank-maximal matching of a bipartite graph with capacities on the right side of the bipartite graph.

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. Nodes on the right side of the partition may be matched multiple times. This is why the user must provide a capacity function on the nodes plus a partition of the nodes such that all edges are from A to B.

The matching is returned as a list of edges. The running time is $O(n m)$ .

During the algorithm the input graph is copied and everything happens on the copy.

Parameters

G	The graph
A	Nodes of the left-side partition of the bipartite graph.
B	Nodes of the right-side partition of the bipartite graph.
capacity	Node capacities
rank	A rank function on the edges.

Precondition: G must be simple, loopfree and bipartite.; rank is a positive integer function on the edges of the graph.; Capacities must be positive.; Capacities of all nodes of the left-side partition must be 1.

Returns: The list of edges of the computed matching.

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

Compute a rank-maximal matching of a bipartite graph.

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(r \sqrt{n} m)$ where $r$ is the maximum rank of an edge in the input.

Parameters

G	The graph
rank	A rank function on the edges.

Precondition: G must be simple, loopfree and bipartite.; rank is a positive integer function on the edges of the graph.

Returns: A list of edges with the resulting matching.

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

Compute a rank-maximal matching of a bipartite graph.

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^2 ( 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^n$ . The space requirement is $O(mn + n^2)$ .

Parameters

G	The graph
rank	A rank function on the edges.

Precondition: G must be simple, loopfree and bipartite.; rank is a positive integer function on the edges of the graph.

Returns: A list of edges with the resulting matching.

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

Compute the profile of a 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.

Parameters

G	The input bipartite graph.
rank	An edge rank function.
matching	A matching.

Returns: The profile of the input matching.

Precondition: rank is a positive integer function on the edges of the graph.

leda::list<leda::edge> mosp::DBI_RANK_MAX_MATCHING_MWMR	(	leda::graph &	G,
		const leda::edge_array< int > &	rank
	)

Compute a rank-maximal matching of a bipartite graph.

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. The reduction is implicit resulting to a running time of $(r \sqrt{n} m )$ where $r$ is the maximum rank of an edge in the input and linear space.

Parameters

G	The graph
rank	A rank function on the edges.

Precondition: G must be simple, loopfree and bipartite.; rank is a positive integer function on the edges of the graph.

Returns: A list of edges with the resulting matching.

Functions

Detailed Description

Function Documentation