On the (co)girth of a connected matroid Academic Article uri icon

abstract

  • This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids. 2007 Elsevier B.V. All rights reserved.

published proceedings

  • DISCRETE APPLIED MATHEMATICS

altmetric score

  • 3

author list (cited authors)

  • Cho, J. J., Chen, Y., & Ding, Y. u.

citation count

  • 16

complete list of authors

  • Cho, Jung Jin||Chen, Yong||Ding, Yu

publication date

  • January 2007