Graph AlgorithMS using Rank and Determinant

Abstract

Algebraic algorithms are important since they provide elegant and easy solutions to many problems. Even though most fast algorithms for graph problems exploit graphs structure or combinatorial properties, in some situations algebraic solutions out perform these algorithms. Also with future improvements to the basic matrix al- gorithms and with novel parallel algorithms emerging, algebraic algorithms are set to become faster. In this thesis I explore important algebraic graph theoretic algorithms. All the algorithms discussed here use the same tool at their core i.e. equivalence of computing the determinant, multiplying two matrices, inverting a matrix, and per- forming Gaussian Elimination. All of these operations take time O(nω ), where ω is the matrix multiplication constant (< 2.373)[1]. Problems discussed are Existence of Bipartite Perfect Matchings, Size of Maximum Bipartite Matching, Counting perfect matchings in planar graphs and counting the number of spanning trees.