The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

John Kececioglu's research software

A matching of a graph is a subset of the edges in which no two edges touch a common vertex. An implementation of Edmonds' algorithm for computing a maximum cardinality matching of a general graph is available here. Given a graph of n vertices and m edges, the implementation runs in O(m n a(m,n)) time, where a(m,n), an inverse of Ackermann's function, is the amortized time per operation of the disjoint set data structure.
  • Download Files (local site)
  • Offical Site

    Problem Links

    Matching (7)

    This page last modified on 2008-07-10 .