RECOGNIZING A CLASS OF BICIRCULAR MATROIDS

This paper presents a polynomial-time algorithm for solving a restrict ed version of the recognition problem for bicircular matroids. Given a matroid M, the problem is to determine whether M is bicircular. Chand ru, 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 mai n theoretical contribution of the paper is a set of necessary and suff icient conditions for a given matroid to be the bicircular matroid of a given graph. As a final result, the complexity result of Chandru et al. is strenghtened.