An O(VE) algorithm for ear decompositions of matching-covered graphs

Abstract

Our main result is an O(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, improving on the previous best running time of O(nm2). where n and m denote the number of nodes and edges. The improvement in the running time comes from new structural results that give a sharpened version of Lovasz and Plummer's Two-ear Theorem. Our algorithm is based on O(nm)-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. (To the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.)