A sublinear parallel algorithm for stable matching

Authors
Feder, T Megiddo, N Plotkin, SA
Citation
T. Feder et al., A sublinear parallel algorithm for stable matching, THEOR COMP, 233(1-2), 2000, pp. 297-308
Citations number
8
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
233
Issue
1-2
Year of publication
2000
Pages
297 - 308
Database
ISI
SICI code
0304-3975(20000228)233:1-2<297:ASPAFS>2.0.ZU;2-L
Abstract
A parallel algorithm for the stable matching problem is presented. The algo rithm is based on the primal-dual interior path-following method for linear programming. The main result is that st stable matching can be found in O* (root m) time by a polynomial number of processors, where m is the total le ngth of preference lists of individuals. (C) 2000 Published by Elsevier Sci ence B.V. All rights reserved.