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.
