@techreport{TR-IC-96-09,
  number = {IC-96-09},
  author = {Setubal, João C.},
  title = {Sequential and Parallel Experimental Results with Bipartite Matching Algorithms},
  month = {September},
  year = {1996}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 23 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      We present experimental results for four bipartite matching
      algorithms on 11 classes of graphs.  The algorithms are
      depth-first search (DFS), breadth-first search (BFS), the
      push-relabel algorithm, and the algorithm by Alt, Blum,
      Mehlhorn, and Paul (ABMP).  DFS was thought to be a good choice
      for bipartite matching but our results show that, depending on
      the input graph, it can have very poor performance. BFS on the
      other hand has generally very good performance.  The results
      also show that the ABMP and push-relabel implementations are
      similar in performance, but {ABMP} was faster in most cases. We
      did not find a clear-cut advantage of ABMP over BFS or
      vice-versa, but both the ABMP and push-relabel implementations
      have generally smaller growth rates than BFS, and should thus be
      preferred if very large problems are to be solved. For small
      problems BFS is the best choice. We also present experimental
      results from a parallel implementation of the push-relabel
      algorithm, showing that it can be up to three times faster than
      its sequential implementation, on a shared-memory multiprocessor
      using up to 12 processors.
  }
}