Computing girth and cogirth in perturbed graphic matroids

Abstract

We give polynomial-time randomized algorithms for computing the girth and the cogirth of binary matroids that are low-rank perturbations of graphic matroids.

arXiv comment24 pages, no figures