Show simple item record

dc.contributor.advisor Hicks, Illya V
dc.creatorArellano, John David
dc.date.accessioned 2016-01-06T20:08:18Z
dc.date.available 2016-01-06T20:08:18Z
dc.date.created 2014-12
dc.date.issued 2014-09-18
dc.date.submitted December 2014
dc.identifier.citation Arellano, John David. "Algorithms to Find the Girth and Cogirth of a Linear Matroid." (2014) Diss., Rice University. http://hdl.handle.net/1911/87699.
dc.identifier.urihttp://hdl.handle.net/1911/87699
dc.description.abstract 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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectset covering
linear matroid
cogirth
girth
dc.title Algorithms to Find the Girth and Cogirth of a Linear Matroid
dc.contributor.committeeMember Tapia, Richard A
dc.contributor.committeeMember Yin, Wotao
dc.contributor.committeeMember Baraniuk, Richard G
dc.date.updated 2016-01-06T20:08:18Z
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record