FINDING MAXIMUM MATCHING FOR BIPARTITE GRAPHS IN PARALLEL

Authors
CHAUDHURI P
Citation
P. Chaudhuri, FINDING MAXIMUM MATCHING FOR BIPARTITE GRAPHS IN PARALLEL, Operations research letters, 16(1), 1994, pp. 47-49
Citations number
9
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
16
Issue
1
Year of publication
1994
Pages
47 - 49
Database
ISI
SICI code
0167-6377(1994)16:1<47:FMMFBG>2.0.ZU;2-#
Abstract
This paper shows that the maximum matching problem on bipartite graphs can be solved in O(n(log log n)2) time with O(n3/log log n) processor s on a single instruction stream, multiple data stream (SIMD) computer that allows both read and write conflicts.