A Linear-Time Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs

Let G = (U,V,E) be a bipartite graph with |E| = m, U union V = {v(subscript 1),..., v(subscript 2n)} and with the bipartition U consisting of all odd indexed vertices and V consisting of all even indexed vertices. An edge in G is always assumed to be oriented towards the endpoint with the larger index. We refer to the up (resp. down) edges of G as the edges which are oriented from an even (resp. odd) indexed vertex. If all the up edges are nested among themselves and among the down edges we say G is a skew graph. The main result of this paper is to give an O(m) algorithm to enumerate perfect matchings in skew graphs. Applications to outerplanar graphs and some problems in chemistry are given.

P. Dagum