An adjustable linear time parallel algorithm for maximun weight bipartite matching

We present a parallel algorithm for finding a maximum weight matching in general bipartite graphs with an adjustable time complexity of Click to view the MathML source using O(nmax(2?,4+?)) processing elements for ?greater-or-equal, slanted1. Parameter ? is not bounded. This is the fastest known str...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2006-03, Vol.97 (5), p.186
Main Authors: Fayyazi, Morteza, Kaeli, David, Meleis, Waleed
Format: Article
Language:English
Subjects:
Algorithms
Graph algorithms
Mathematical analysis
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a parallel algorithm for finding a maximum weight matching in general bipartite graphs with an adjustable time complexity of Click to view the MathML source using O(nmax(2?,4+?)) processing elements for ?greater-or-equal, slanted1. Parameter ? is not bounded. This is the fastest known strongly polynomial parallel algorithm to solve this problem. This is also the first adjustable parallel algorithm for the maximum weight bipartite matching problem in which the execution time can be reduced by an unbounded factor. We also present a general approach for finding efficient parallel algorithms for the maximum matching problem. [PUBLICATION ABSTRACT]
ISSN:0020-0190
1872-6119