Publication Details
Title: A Linear-Time Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs
Author: P. Dagum
Group: ICSI Technical Reports
Date: February 1989
PDF: [Not available online]
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-007
Bibliographic Reference:
P. Dagum. A Linear-Time Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs. ICSI Technical Report TR-89-007, February 1989
Author: P. Dagum
Group: ICSI Technical Reports
Date: February 1989
PDF: [Not available online]
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-007
Bibliographic Reference:
P. Dagum. A Linear-Time Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs. ICSI Technical Report TR-89-007, February 1989