Algorithms to Find the Girth and Cogirth of a Linear Matroid
Arellano, John David
Hicks, Illya V
Doctor of Philosophy
In this thesis, I present algorithms to find the cogirth and girth, the cardinality of the smallest cocircuit and circuit respectively, of a linear matroid. A set covering problem (SCP) formulation of the problems is presented. The solution to the linear matroid cogirth problem provides the degree of redundancy of the corresponding sensor network, and allows for the evaluation of the quality of the network. Hence, addressing the linear matroid cogirth problem can lead to significantly enhancing the design process of sensor networks. The linear matroid girth problem is related to reconstructing a signal in compressive sensing. I provide an introduction to matroids and their relation to the degree of redundancy problem as well as compressive sensing. I also provide an overview of the methods used to address linear matroid cogirth/girth problems, the SCP, and reconstructing a signal in compressive sensing. Computational results are provided to validate a branch-and-cut algorithm that addresses the SCP formulation as well as an algorithm which uses branch decompositions and dynamic programming to find the girth of a linear matroid.
set covering; linear matroid; cogirth; girth