Show simple item record

dc.contributor.advisor Hicks, Illya V.
dc.creatorMa, Jing
dc.date.accessioned 2011-07-25T02:07:21Z
dc.date.available 2011-07-25T02:07:21Z
dc.date.issued 2010
dc.identifier.urihttps://hdl.handle.net/1911/62192
dc.description.abstract This thesis present two new heuristics which utilize classification and max-flow algorithm respectively to derive near-optimal branch-decompositions for linear matroids. In the literature, there are already excellent heuristics for graphs, however, no practical branch-decomposition methods for general linear matroids have been addressed yet. Introducing a "measure" which compares the "similarity" of elements of a linear matroid, this work reforms the linear matroid into a similarity graph. Then, two different methods, classification method and max-flow method, both basing on the similarity graph are developed into heuristics. Computational results using the classification method and the max-flow method on linear matroid instances are shown respectively.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectApplied mathematics
Mathematics
dc.title Branch-decomposition heuristics for linear matroids
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Chemistry
thesis.degree.discipline Natural Sciences
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Arts
dc.identifier.citation Ma, Jing. "Branch-decomposition heuristics for linear matroids." (2010) Master’s Thesis, Rice University. https://hdl.handle.net/1911/62192.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record