ALGORITHMS FOR VERTEX-WEIGHTED MATCHING IN GRAPHS

A matching M in a graph is a subset of edges such that no two edges in M are inci-dent on the same vertex. Matching is a fundamental combinatorial problem that has applications in many contexts: high-performance computing, bioinformatics, net-work switch design, web technologies, etc. Examples in the first context include sparse linear systems of equations, where matchings are used to place large matrix elements on or close to the diagonal, to compute the block triangular decomposition of sparse matrices, to construct sparse bases for the null space or column space of under-determined matrices, and to coarsen graphs in multi-level graph partitioning algorithms. In the first part of this thesis, we develop exact and approximation al-gorithms for vertex weighted matchings, an under-studied variant of the weighted matching problem. We propose three exact algorithms, three half approximation algorithms, and a two-third approximation algorithm. We exploit inherent proper-ties of this problem such as lexicographical orders, decomposition into sub-problems, and the reachability property, not only to design efficient algorithms, but also to provide simple proofs of correctness of the proposed algorithms. In the second par