Recognizing a class of bicircular matroids

AbstractThis paper presents a polynomial-time algorithm for solving a restricted version of the recognition problem for bicircular matroids. Given a matroid M, the problem is to determine whether M is bicircular. Chandru, Coullard and Wagner showed that this problem is NP-hard in general. The main tool in the development of the algorithm as well as the main theoretical contribution of the paper is a set of necessary and sufficient conditions for a given matroid to be the bicircular matroid of a given graph. As a final result, the complexity result of Chandru is strenghtened