Stable Marriage problem is a classical problem in matching theory. In this problem we have a set of n men and n women, each person having his or her own preference list of persons he or she wants to marry, and we have to determine an assignment of each man to some woman so that there does not exist any pair who are not matched but prefer each other than their current partners. We address a stable marriage problem where each of the persons have equal favour at the time of assignment. We give an O(n2.5 log n) time algorithm to solve this problem. This improves the previous result of O(n3). We also provide a reduction of vertex cover problem to a stable marriage problem. Given a graph G with n vertices, we can construct an instance of stable marriage problem, such that each solution to the stable marriage will correspond to a solution to the vertex cover in the original graph.
We give approximation algorithms to determine the minimum feedback vertex set for butterfly and toroidal butterfly topology which runs in linear time and approximates the lower bound of 2k-1[(k+1)/2] to a factor of 1+1/3.
Full Thesis (PS gzipped 231K)