A Family of Bipartite |Cardinality Matching Problems Solvable in O(n\^2) Time

Jens Clausen; J. Krarup

A Family of Bipartite |Cardinality Matching Problems Solvable in O(n\^2) Time

Jens Clausen
, J. Krarup

Research output: Contribution to journal › Journal article › Research › peer-review

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(n/sup 5/2/ ). We devise a greedy algorithm which either finds a perfect matching in O(n/sup 2/ ) time or identifies cycle of length 4 in the complement G of G

Original language	English
Journal	Nordic Journal of Computing
Volume	2
Pages (from-to)	496 - 501
ISSN	1236-6064
Publication status	Published - 1995

Access to Document

http://www2.imm.dtu.dk/pubdb/p.php?580

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{5f39568e88e84c7cbb037fb7c1d84525,

title = "A Family of Bipartite |Cardinality Matching Problems Solvable in O(n\textbackslash{}\textasciicircum{}2) Time",

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(n/sup 5/2/ ). We devise a greedy algorithm which either finds a perfect matching in O(n/sup 2/ ) time or identifies cycle of length 4 in the complement G of G",

author = "Jens Clausen and J. Krarup",

year = "1995",

language = "English",

volume = "2",

pages = "496 -- 501",

journal = "Nordic Journal of Computing",

issn = "1236-6064",

publisher = "University of Helsinki Department of Computer Science",

}

TY - JOUR

T1 - A Family of Bipartite |Cardinality Matching Problems Solvable in O(n\^2) Time

AU - Clausen, Jens

AU - Krarup, J.

PY - 1995

Y1 - 1995

N2 - 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(n/sup 5/2/ ). We devise a greedy algorithm which either finds a perfect matching in O(n/sup 2/ ) time or identifies cycle of length 4 in the complement G of G

AB - 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(n/sup 5/2/ ). We devise a greedy algorithm which either finds a perfect matching in O(n/sup 2/ ) time or identifies cycle of length 4 in the complement G of G

M3 - Journal article

SN - 1236-6064

VL - 2

SP - 496

EP - 501

JO - Nordic Journal of Computing

JF - Nordic Journal of Computing

ER -

A Family of Bipartite |Cardinality Matching Problems Solvable in O(n\^2) Time

Abstract

Access to Document

OpenUrl availability

Fingerprint

Cite this