What is it?

Given a bipartite graph G(V,E), V = A &cup B and a partition of the edge set into at most n disjoint sets (called ranks), we want to compute a matching M such that it contains the maximum number of rank 1 edges and given that constraint the maximum number of rank 2 edges and so on.

Algorithms

There are two algorithms implemented in this package.

The first is based on:

  • R. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch.
    Rank-maximal matchings. [ps.gz]
    In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)
The running time is O(C &radic n m) and the space linear. Here n is the number of vertices, m the number of edges and C is the largest rank used in the optimal solution.

The second is a reduction to the maximum weight matching problem with running time O( n2 ( m + n logn ) ) and space O( mn + n2 ). The extra n comes from the possible cost of arithmetic since the algorithm handles numbers up to O( nn ).

Requirements

This implementation is written in C++ and uses LEDA. The structure of the package follows that of a LEDA extension package (LEP).

Supported Platforms

This package has been tested on the following platforms:
  • gcc 3.x under Linux, SunOS 5.9, Cygwin
  • bcc32 5.5 under Windows
but it may work on others too.

License

This program can be freely used in an academic environment ONLY for research purposes, subject to the following restrictions:
  1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software an acknowledgment in the product documentation is required.
  2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.
Any other use is strictly prohibited by the author, without an explicit permission.

This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Note that this package uses LEDA, which is not free.

News

  • 24 Apr 2005: v0.6 released
    • support LEDA 5.0 on win32 platforms with bcc32
    • minor fixes
  • 23 Feb 2005: v0.5 released
    • support Borland C++ bcc32 compiler (only LEDA 4.5 or earlier)
  • 11 Feb 2005: v0.3 released
    • support for LEDA-5.0 added, see INSTALL file
  • 19 Oct 2004: v0.2 released
  • 23 Sep 2004: v0.1 released

Documentation

Download

  • Source package (v0.6). [tar.gz]
  • Source package (v0.5). [tar.gz]
  • Source package (v0.3). [tar.gz]
  • Source package (v0.2). [tar.gz]

Code Example


#include < LEP/rmm/RANK_MAX_MATCHING.h >

int main() {
  leda::graph G;

  /* construct simple loopfree bipartite graph */
	
  leda::edge_array< int > rank(G,1);

  /* fill up ranks */
	
  leda::list< leda::edge > M = BI_RANK_MAX_MATCHING( G, rank );
	
  return 0;
}

Contact

For bugs or suggestions please contact me at