Separating cocircuits in binary matroids |
| |
Authors: | William H Cunningham |
| |
Institution: | Department of Mathematics and Statistics Carleton University Ottawa, Canada K1S 5B6, USA |
| |
Abstract: | A cocircuit of a matroid is separating if deleting it leaves a separable matroid. We give an effecient algorithm which finds a separating cocircuit or a Fano minor in a binary matroid, thus proving constructively a theorem of Tutte. Using this algorithm and a new recursive characterization of bond matroids, we give a new method for testing binary matroids for graphicness. We also give an efficient algorithm for finding a special kind of separating cocircuit: one whose deletion leaves a matroid having a coloop. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|