Nordic Journal of Computing Bibliography

J. Clausen and J. Krarup. A Family of Bipartite Cardinality Matching Problems Solvable in O(n2) Time. Nordic Journal of Computing, 2(4):496-501, Winter 1995.
Abstract

For a given, unweighted bipartite graph G with 2n non-isolated vertices, we consider the so-called Bipartite Cardinality Matching Problem (BCMP) for which the time complexity of the fastest exact algorithm available is O(n5/2). We devise a greedy algorithm which either finds a perfect matching in O(n2) time or identifies cycle of length 4 in the complement \bar{G} of G.

Categories and Subject Descriptors: G.1.6 [Numerical Analysis]: Optimization; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: bipartite cardinality matching, greedy algorithm

Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database