Journal article
On the (co)girth of a connected matroid
Discrete Applied Mathematics, Vol.155(18), pp.2456-2470
2007
DOI: 10.1016/j.dam.2007.06.015
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.
Details
- Title: Subtitle
- On the (co)girth of a connected matroid
- Creators
- Jung Jin Cho - Texas A&M UniversityYong Chen - University of IowaYu Ding - Texas A&M University
- Resource Type
- Journal article
- Publication Details
- Discrete Applied Mathematics, Vol.155(18), pp.2456-2470
- DOI
- 10.1016/j.dam.2007.06.015
- ISSN
- 0166-218X
- eISSN
- 1872-6771
- Publisher
- Elsevier B.V
- Language
- English
- Date published
- 2007
- Academic Unit
- Industrial and Systems Engineering
- Record Identifier
- 9984186951302771
Metrics
10 Record Views