Computing girth and cogirth in perturbed graphic matroids

2015/04/28 by Geelen, Jim, Kapadia, Rohan · 1 citation
#05B35 (Primary) #90C27 (Secondary) #94B05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1504.07647

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.

Cited by

• On Finding ℓ-th Smallest Perfect Matchings

Related

• On the Cogirth of Binary Matroids
• Prohibited Minors For Graphic Matroids That Gives A Binary Gammoid After Splitting
• Decomposition of Quaternary Signed-Graphic Matroids
• Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
• Describing Quasi-Graphic Matroids