Survey of AlgorithMS for Different Matchings

Abstract

The main aim of this project is to survey some techniques used to develop algorithms to find di↵erent types of matchings. The three main papers that we survey are: 1. Bipartite Perfect Matching is in quasi-NC- Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf. This paper gave a technique to derandomize the famous isolation lemma using (n6 log n) processors working in parallel to find a perfect matching in a bipartite Graph 2. The Matching Problem in General Graphs is in Quasi-NC- Ola Svensson, Jakub Tarnawski. This paper built on the tecniques of the previous paper to give a quasi-NC algorithm to find a perfect matching in General graphs. 3. Popular Matchings.- David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn. This was one of the first papers to give a polynomial time algorithm to find popular matching in bipartite graphs where nodes in one partition have preferences regarding which node in the other partition to be matched to .